{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T22:29:00Z","timestamp":1767911340925,"version":"3.49.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1993,9,1]],"date-time":"1993-09-01T00:00:00Z","timestamp":746841600000},"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":[[1993,9]]},"DOI":"10.1007\/bf01371727","type":"journal-article","created":{"date-parts":[[2005,4,1]],"date-time":"2005-04-01T23:51:18Z","timestamp":1112399478000},"page":"237-269","source":"Crossref","is-referenced-by-count":49,"title":["State-complexity of finite-state devices, state compressibility and incompressibility"],"prefix":"10.1007","volume":"26","author":[{"given":"Jean-Camille","family":"Birget","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"The Theory of Parsing, Translation and Compiling, Vol. 1","author":"A. Aho","year":"1972","unstructured":"A. Aho, J. Ullman,The Theory of Parsing, Translation and Compiling, Vol. 1, Prentice-Hall, Englewood Cliffs, NJ, 1972."},{"key":"CR2","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,Theoret. Comput. Sci.,63 (1989), 141?156.","journal-title":"Theoret. Comput. Sci."},{"key":"CR3","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,J. Comput. System Sci. (special issue onSTOC 89),45 (1992), 154?179.","journal-title":"J. Comput. System Sci. (special issue on STOC 89)"},{"key":"CR4","unstructured":"J. C. Birget, Two-way automata and length-preserving homomorphisms, Report # 109, Dept. of Computer Science, University of Nebraska (1990) (submitted)."},{"key":"CR5","unstructured":"J. C. Birget, The minimum automaton of certain languages (in preparation)."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1142\/S0218196791000092","volume":"1","author":"J. C. Birget","year":"1991","unstructured":"J. C. Birget, Strict local testability of the finite control of two-way automata and of regular picture description languages,Internat. J. Algebra Comput.,1 (1991), 161?175.","journal-title":"Internat. J. Algebra Comput."},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"J. C. Birget, Partial order on words, minimal elements of a regular language, and state-complexity,Theoret. Comput. Sci. (to appear).","DOI":"10.1016\/0304-3975(93)90160-U"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0020-0190(92)90198-5","volume":"43","author":"J. C. Birget","year":"1992","unstructured":"J. C. Birget, Intersection and union of regular languages and state-complexity,Inform. Process. Lett.,43 (1992), 185?190.","journal-title":"Inform. Process. Lett."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"M. Blum, C. Hewitt, Automata on a 2-dimensional tape,Proc. 8th IEEE Symp. on Switching and Automata Theory, 1965, pp. 155?160.","DOI":"10.1109\/FOCS.1967.6"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01705890","volume":"4","author":"R. Book","year":"1970","unstructured":"R. Book, S. Greibach, Quasi-realtime languages,Math. System Theory,4 (1970), 97?111.","journal-title":"Math. System Theory"},{"key":"CR11","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, E. Leiss, On equations for regular languages, finite automata, and sequential networks,Theoret. Computer Sci.,10 (1980), 19?35.","journal-title":"Theoret. Computer Sci."},{"key":"CR12","first-page":"198","volume":"42","author":"J. Brzozowski","year":"1990","unstructured":"J. Brzozowski, C. Seger, Advances in asynchronous circuit theory, Part 1,Bull. EATCS,42 (1990), 198?249.","journal-title":"Advances in asynchronous circuit theory, Part 1, Bull. EATCS"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"A. Chandra, D. Kozen, L. Stockmeyer, Alternation,J. Assoc. Comput. Mach.,28 (1981), 114?133.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"A. Chandra, L. Stockmeyer, Alternation,Proc. 17th IEEE Symp. on Foundations of Computer Sci., 1976, pp. 98?108.","DOI":"10.1109\/SFCS.1976.4"},{"key":"CR15","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,Theoret. Comput. Sci.,47 (1986), 149?158.","journal-title":"Theoret. Comput. Sci."},{"key":"CR16","volume-title":"Automata, Languages, and Machines, Vol. A","author":"S. Eilenberg","year":"1974","unstructured":"S. Eilenberg,Automata, Languages, and Machines, Vol. A, Academic Press, New York, 1974."},{"key":"CR17","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 Turning machine computations,Inform. and Control,8 (1965), 553?578.","journal-title":"Inform. and Control"},{"key":"CR18","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"J. Hopcroft","year":"1979","unstructured":"J. Hopcroft, J. Ullman,Introduction to Automata Theory, Languages and Computation, Addison-Wesely, Reading, MA, 1979."},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"R. Kannan, Alternation and the power of non-determinism,Proc. 15th ACM Symp. on Theory of Computing, 1983, 344?346.","DOI":"10.1145\/800061.808764"},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"D. Kozen, On parallelism in Turing machines,Proc. 17th IEEE Symp. on Foundations of Computer Sci 1976, pp. 89?97.","DOI":"10.1109\/SFCS.1976.20"},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"R. Ladner, R. Lipton, L. Stockmeyer, Alternating pushdown automata,Proc. 19th IEEE Symp. on Foundations of Computer Sciences 1978, pp. 92?106, andSIAM J. Comput.,13(1) (1984), 135?155.","DOI":"10.1137\/0213010"},{"key":"CR22","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,Theoret. Comput. Sci.,13(1981), 323?330.","journal-title":"Theoret. Comput. Sci."},{"key":"CR23","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,Theoret. Comput. Sci.,38 (1985), 133?136.","journal-title":"Theoret. Comput. Sci."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/0304-3975(85)90021-0","volume":"35","author":"E. Leiss","year":"1985","unstructured":"E. Leiss, A class of tractable unrestricted regular expressions,Theoret. Comput. Sci.,35 (1985), 313?327.","journal-title":"Theoret. Comput. Sci."},{"key":"CR25","volume-title":"Counter-free Automata","author":"R. McNaughton","year":"1971","unstructured":"R. McNaughton, S. Papert,Counter-free Automata, MIT Press, Cambridge, MA, 1971."},{"key":"CR26","doi-asserted-by":"crossref","unstructured":"A. R. Meyer, M. J. Fischer, Economy of description by automata, grammars, and formal systems,Proc. 21st IEEE Symp. on Switching and Automata Theory, 1971, pp. 188?191.","DOI":"10.1109\/SWAT.1971.11"},{"key":"CR27","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M. Rabin","year":"1959","unstructured":"M. Rabin, D. Scott, Finite automata and their decision problems,IBM J. Res. Develop.,3 (1959), 114?125; also in E. F. Moore (ed.),Sequential Machines: Selected Papers, Addison-Wesley, Reading, MA, 1964.","journal-title":"IBM J. Res. Develop."},{"key":"CR28","doi-asserted-by":"crossref","unstructured":"W. Sakoda, M. Sipser, Non-determinism and the size of two-way automata,Proc. 10th ACM Symp. on Theory of Computing, 1978, pp. 275?286.","DOI":"10.1145\/800133.804357"},{"key":"CR29","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1147\/rd.32.0198","volume":"3","author":"J. C. Shepherdson","year":"1959","unstructured":"J. C. Shepherdson, The reduction of two-way automata to one-way automata,IBM J. Res. Develop.,3 (1959), 198?200; also in E. F. Moore (ed.),Sequential Machines: Selected Papers, Addison-Wesley, Reading, MA, 1964.","journal-title":"IBM J. Res. Develop."},{"key":"CR30","doi-asserted-by":"crossref","unstructured":"M. Sipser, Lower bounds on the size of sweeping machines,Proc. 11th ACM Symp. on Theory of Computing, 1979, pp. 360?364; andJ. Comput. System Sci.,21 (1980), 195?202.","DOI":"10.1145\/800135.804429"},{"key":"CR31","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,Theoret. Comput. Sci.,10 (1980), 335?338 alsoProc. 19th IEEE Symp. on Foundations of Computer Science, 1978.","journal-title":"Theoret. Comput. Sci."},{"key":"CR32","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0020-0190(89)90205-6","volume":"30","author":"M. Vardi","year":"1989","unstructured":"M. Vardi, A note on the reduction of two-way automata to one-way automata,Inform. Process. Lett.,30 (1989), 261?264.","journal-title":"Inform. Process. Lett."}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01371727.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01371727\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01371727","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,30]],"date-time":"2024-12-30T01:38:06Z","timestamp":1735522686000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01371727"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,9]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1993,9]]}},"alternative-id":["BF01371727"],"URL":"https:\/\/doi.org\/10.1007\/bf01371727","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,9]]}}}