{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:20Z","timestamp":1759638380915,"version":"3.32.0"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1996,6,1]],"date-time":"1996-06-01T00:00:00Z","timestamp":833587200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1996,6]]},"DOI":"10.1007\/bf01201276","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T12:15:55Z","timestamp":1108728955000},"page":"191-226","source":"Crossref","is-referenced-by-count":8,"title":["Two-way automata and length-preserving homomorphisms"],"prefix":"10.1007","volume":"29","author":[{"given":"J. -C.","family":"Birget","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01201276_CR1","volume-title":"Introduction to Analytic Number Theory","author":"T. Apostol","year":"1976","unstructured":"T. Apostol,Introduction to Analytic Number Theory, Springer-Verlag, New York, 1976."},{"key":"BF01201276_CR2","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. Aho","year":"1974","unstructured":"A. Aho, J. Hopcroft, and J. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"BF01201276_CR3","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0304-3975(89)90075-3","volume":"63","author":"J.-C. Birget","year":"1989","unstructured":"J.-C. Birget, Concatenation of inputs in a two-way automaton,Theoretical Computer Science 63 (1989), 141\u2013156.","journal-title":"Theoretical Computer Science"},{"key":"BF01201276_CR4","series-title":"Lecture Notes in Computer Science, Vol. 386","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/BFb0013111","volume-title":"Formal Properties of Finite Automata and Applications","author":"J.-C. Birget","year":"1989","unstructured":"J.-C. Birget, Basic techniques for two-way finite automata, in: J. E. Pin (ed.),Formal Properties of Finite Automata and Applications, Lecture Notes in Computer Science, Vol. 386, Springer-Verlag, Berlin, 1989, pp. 56\u201364."},{"key":"BF01201276_CR5","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/0022-0000(92)90045-K","volume":"45","author":"J.-C. Birget","year":"1992","unstructured":"J.-C. Birget, Positional simulation of two-way automata: proof of a conjecture of R. Kannan, and generalizations,Journal of Computer and System Sciences 45 (1992), 154\u2013179 (special issue onSTOC 89).","journal-title":"Journal of Computer and System Sciences"},{"key":"BF01201276_CR6","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/BF01371727","volume":"26","author":"J.-C. Birget","year":"1993","unstructured":"J.-C. Birget, State-complexity of finite-state devices, state-compressibility and incompressibility,Mathematical Systems Theory 26 (1993), 237\u2013269.","journal-title":"Mathematical Systems Theory"},{"key":"BF01201276_CR7","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0304-3975(93)90160-U","volume":"119","author":"J.-C. Birget","year":"1993","unstructured":"J.-C. Birget, Partial orders on words, minimal elements in regular languages, and state complexity,Theoretical Computer Science,119 (1993), 267\u2013291.","journal-title":"Theoretical Computer Science"},{"key":"BF01201276_CR8","unstructured":"J.-C. Birget, The minimum automaton for certain languages, in preparation."},{"key":"BF01201276_CR9","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01705890","volume":"4","author":"R. Book","year":"1970","unstructured":"R. Book and S. Greibach, Quasi-realtime languages,Mathematical Systems Theory 4 (1970), 97\u2013111.","journal-title":"Mathematical Systems Theory"},{"key":"BF01201276_CR10","doi-asserted-by":"crossref","unstructured":"M. Blum and C. Hewitt, Automata on a 2-dimensional tape,Proceedings of the 8th IEEE Symposium on Switching and Automata Theory, 1965, pp. 155\u2013160.","DOI":"10.1109\/FOCS.1967.6"},{"key":"BF01201276_CR11","doi-asserted-by":"crossref","unstructured":"D. A. M. Barrington, K. Compton, H. Straubing, and D. Th\u00e9rien, Regular languages in NC1,Journal of Computer and System Sciences, to appear.","DOI":"10.1016\/0022-0000(92)90014-A"},{"key":"BF01201276_CR12","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0304-3975(80)90069-9","volume":"10","author":"J. Brzozowski","year":"1980","unstructured":"J. Brzozowski and E. Leiss, On equations for regular languages, finite automata, and sequential networks,Theoretical Computer Science 10 (1980), 19\u201335.","journal-title":"Theoretical Computer Science"},{"key":"BF01201276_CR13","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D. A. M. Barrington","year":"1988","unstructured":"D. A. M. Barrington and D. Th\u00e9rien, Finite monoids and the fine structure of NC1,Journal of the Association for Computing Machinery 35 (1988), 941\u2013952.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF01201276_CR14","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","volume":"47","author":"M. Chrobak","year":"1986","unstructured":"M. Chrobak, Finite automata and unary languages,Theoretical Computer Science 47 (1986), 149\u2013158.","journal-title":"Theoretical Computer Science"},{"key":"BF01201276_CR15","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"A. Chandra, D. Kozen, and L. Stockmeyer, Alternation,Journal of the Association for Computing Machinery 28 (1981), 114\u2013133.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF01201276_CR16","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. Cook","year":"1985","unstructured":"S. Cook, A taxonomy of problems with fast parallel algorithms,Information and Control 64 (1985), 2\u201322.","journal-title":"Information and Control"},{"key":"BF01201276_CR17","doi-asserted-by":"crossref","unstructured":"A. Chandra and L. Stockmeyer, Alternation,Proceedings of the 17thIEEE Annual Symposium on Foundations of Computer Science, 1976, pp. 98\u2013108.","DOI":"10.1109\/SFCS.1976.4"},{"key":"BF01201276_CR18","volume-title":"Machines, Languages, and Computation","author":"P. Denning","year":"1978","unstructured":"P. Denning, J. Dennis, and J. Qualitz,Machines, Languages, and Computation, Prentice-Hall, Englewood Cliffs, NJ, 1978."},{"key":"BF01201276_CR19","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/0020-0190(91)90208-Y","volume":"38","author":"P. Goral\u010d\u00edk","year":"1991","unstructured":"P. Goral\u010d\u00edk, A. Goral\u010d\u00edkov\u00e1, and V. Koubek, Alternation with a pebble,Information Processing Letters 38 (1991), 7\u201313.","journal-title":"Information Processing Letters"},{"key":"BF01201276_CR20","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1016\/S0019-9958(65)90399-2","volume":"8","author":"F. C. Hennie","year":"1965","unstructured":"F. C. Hennie, One-tape off-line Turing machine computations,Information and Control 8 (1965), 553\u2013578.","journal-title":"Information and Control"},{"key":"BF01201276_CR21","doi-asserted-by":"crossref","unstructured":"H. B. Hunt III, On the time and tape complexity of languages, I,Proceedings of the 5th Annual ACM Symposium on Theory of Computing, 1973, pp. 10\u201319.","DOI":"10.1145\/800125.804030"},{"key":"BF01201276_CR22","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"J. Hopcroft","year":"1979","unstructured":"J. Hopcroft and J. Ullman,Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, MA, 1979."},{"key":"BF01201276_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02088003","volume":"21","author":"O. Ibarra","year":"1988","unstructured":"O. Ibarra and B. Ravikumar: Sublogarithmic-space Turing machines, nonuniform space complexity, and closure properties,Mathematical Systems Theory 21 (1988), 1\u201317.","journal-title":"Mathematical Systems Theory"},{"key":"BF01201276_CR24","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/S0022-0000(75)80049-3","volume":"11","author":"O. Ibarra","year":"1975","unstructured":"O. Ibarra and S. Sahni, Hierarchies of Turing machines with restricted tape alphabet size,Journal of Computer and System Sciences 11 (1975), 56\u201367.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF01201276_CR25","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0020-0190(05)80006-7","volume":"40","author":"T. Jiang","year":"1991","unstructured":"T. Jiang and B. Ravikumar, A Note on the Space Complexity of Some Decision Problems for Finite Automata,Information Processing Letters 40 (1991), 25\u201331.","journal-title":"Information Processing Letters"},{"key":"BF01201276_CR26","doi-asserted-by":"crossref","unstructured":"R. Kannan, Alternation and the power of non-determinism,Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983, pp. 344\u2013346.","DOI":"10.1145\/800061.808764"},{"key":"BF01201276_CR27","doi-asserted-by":"crossref","unstructured":"D. Kozen, On parallelism in Turing machines,Proceedings of the 17th IEEE Annual Symposium on Foundations of Computer Science, 1976, pp. 89\u201397.","DOI":"10.1109\/SFCS.1976.20"},{"key":"BF01201276_CR28","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/S0304-3975(81)80005-9","volume":"13","author":"E. Leiss","year":"1981","unstructured":"E. Leiss, Succinct representation of regular languages by boolean automata,Theoretical Computer Science 13 (1981), 323\u2013330.","journal-title":"Theoretical Computer Science"},{"key":"BF01201276_CR29","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0304-3975(85)90215-4","volume":"38","author":"E. Leiss","year":"1985","unstructured":"E. Leiss, Succinct representation of regular languages by boolean automata, II,Theoretical Computer Science 38 (1985), 133\u2013136.","journal-title":"Theoretical Computer Science"},{"key":"BF01201276_CR30","doi-asserted-by":"crossref","unstructured":"R. Ladner, R. Lipton, and L. Stockmeyer, Alternating pushdown automata,Proceedings of the 19th IEEE Symposium on Foundations of Computer Science, 1978, pp. 92\u2013106, andSIAM Journal of Computing,13(1) (1984), 135\u2013155.","DOI":"10.1109\/SFCS.1978.6"},{"key":"BF01201276_CR31","doi-asserted-by":"crossref","unstructured":"P. M. Lewis, R. Stearns, and J. Hartmanis, Memory bounds for recognition of context-free and context-sensitive languages,Proceedings of the 6th IEEE Symposium on Switching Circuit Theory and Logical Design, 1965, pp. 191\u2013202.","DOI":"10.1109\/FOCS.1965.14"},{"key":"BF01201276_CR32","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0304-3975(91)90054-6","volume":"85","author":"P. Michel","year":"1991","unstructured":"P. Michel, An NP-complete language accepted in linear time by a one-tape Turing machine,Theoretical Computer Science 85 (1991), 205\u2013212.","journal-title":"Theoretical Computer Science"},{"key":"BF01201276_CR33","doi-asserted-by":"crossref","unstructured":"A. R. Meyer and M. J. Fischer, Economy of description by automata, grammars, and formal systems,Proceedings of the 21st IEEE Symposium on Switching and Automata Theory, 1971, pp. 188\u2013191.","DOI":"10.1109\/SWAT.1971.11"},{"key":"BF01201276_CR34","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1145\/321879.321882","volume":"22","author":"D. E. Muller","year":"1975","unstructured":"D. E. Muller and F. P. Preparata, Bounds to complexities of networks for sorting and switching,Journal of the Association for Computing Machinery 22 (1975), 97\u2013111.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF01201276_CR35","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W. L. Ruzzo","year":"1980","unstructured":"W. L. Ruzzo, Tree-size bounded alternation,Journal of Computer and System Sciences 21 (1980), 218\u2013235.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF01201276_CR36","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W. L. Ruzzo","year":"1981","unstructured":"W. L. Ruzzo, On uniform circuit complexity,Journal of Computer and System Sciences 22 (1981), 365\u2013383.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF01201276_CR37","volume-title":"The Complexity of Computing","author":"John E. Savage","year":"1976","unstructured":"John E. Savage,The Complexity of Computing, Wiley, New York, 1976, reprint by Krieger, 1987."},{"key":"BF01201276_CR38","unstructured":"J. C. Shepherdson, The reduction of two-way automata to one-way automata,IBM Journal of Research and Development (1959), 198\u2013200; also in E. F. Moore (ed.),Sequential Machines: Selected Papers, Addison-Wesley, Reading, MA, 1964."},{"key":"BF01201276_CR39","doi-asserted-by":"crossref","unstructured":"M. Sipser, Lower bounds on the size of sweeping machines,Proceedings of the 11thACM Symposium on Theory of Computing, 1979, pp. 360\u2013364; expanded inJournal of Computer and System Sciences 21 (1980), 195\u2013202.","DOI":"10.1145\/800135.804429"},{"key":"BF01201276_CR40","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0304-3975(80)90053-5","volume":"10","author":"M. Sipser","year":"1980","unstructured":"M. Sipser, Halting space-bounded computations,Theoretical Computer Science 10 (1980), 335\u2013338. (See alsoProc. IEEE FOCS, 1978.)","journal-title":"Theoretical Computer Science"},{"key":"BF01201276_CR41","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0304-3975(76)90082-7","volume":"2","author":"F. N. Springsteel","year":"1976","unstructured":"F. N. Springsteel, \u201cOn the pre-AFL of [logn] space, and related families of languages,Theoretical Computer Science 2 (1976), 295\u2013304.","journal-title":"Theoretical Computer Science"},{"key":"BF01201276_CR42","doi-asserted-by":"crossref","unstructured":"W. Sakoda and M. Sipser, Non-determinism and the size of two-way automata,Proceedings of the 10thACM Symposium on Theory of Computing, 1978, pp. 275\u2013286.","DOI":"10.1145\/800133.804357"},{"volume-title":"Handbook of Theoretical Computer Science, Vol. A","year":"1990","key":"BF01201276_CR43","unstructured":"J. van Leeuwen (ed.),Handbook of Theoretical Computer Science, Vol. A, MIT Press, Cambridge, MA, and Elsevier, Amsterdam, 1990."},{"key":"BF01201276_CR44","volume-title":"The Complexity of Boolean Functions","author":"I. Wegener","year":"1987","unstructured":"I. Wegener,The Complexity of Boolean Functions, Wiley-Teubner Series in Computer Science, Wiley, New York, 1987."}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01201276.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01201276\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01201276","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T12:20:51Z","timestamp":1734956451000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01201276"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,6]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1996,6]]}},"alternative-id":["BF01201276"],"URL":"https:\/\/doi.org\/10.1007\/bf01201276","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"type":"print","value":"0025-5661"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[1996,6]]}}}