{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T05:32:49Z","timestamp":1740461569784,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":71,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153488"},{"type":"electronic","value":"9783642153495"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15349-5_1","type":"book-chapter","created":{"date-parts":[[2010,8,21]],"date-time":"2010-08-21T03:39:27Z","timestamp":1282361967000},"page":"1-23","source":"Crossref","is-referenced-by-count":3,"title":["Descriptional Complexity of (Un)ambiguous Finite State Machines and Pushdown Automata"],"prefix":"10.1007","author":[{"given":"Markus","family":"Holzer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Kutrib","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0020-0190(92)90198-5","volume":"43","author":"J.C. Birget","year":"1992","unstructured":"Birget, J.C.: Intersection and union of regular languages and state complexity. Inform. Process. Lett.\u00a043, 185\u2013190 (1992)","journal-title":"Inform. Process. Lett."},{"key":"1_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-540-70583-3_3","volume-title":"Automata, Languages and Programming","author":"H. Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund, H., Martens, W.: The tractability frontier for NFA minimization. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol.\u00a05126, pp. 27\u201338. Springer, Heidelberg (2008)"},{"key":"1_CR3","unstructured":"Borchardt, I.: Nonrecursive tradeoffs between context-free grammars with different constant ambiguity. Diploma thesis, Universit\u00e4t Frankfurt (1992) (in German)"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(92)90002-W","volume":"97","author":"S. Cho","year":"1992","unstructured":"Cho, S., Huynh, D.T.: The parallel complexity of finite-state automata problems. Inform. Comput.\u00a097, 1\u201322 (1992)","journal-title":"Inform. Comput."},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","volume":"47","author":"M. Chrobak","year":"1986","unstructured":"Chrobak, M.: Finite automata and unary languages. Theoret. Comput. Sci.\u00a047, 149\u2013158 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1016\/S0304-3975(03)00136-1","volume":"302","author":"M. Chrobak","year":"2003","unstructured":"Chrobak, M.: Errata to \u201cfinite automata and unary languages\u201d. Theoret. Comput. Sci.\u00a0302, 497\u2013498 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/BF01776575","volume":"12","author":"P.C. Fischer","year":"1979","unstructured":"Fischer, P.C., Kintala, C.M.R.: Real-time computations with restricted nondeterminism. Math. Systems Theory\u00a012, 219\u2013231 (1979)","journal-title":"Math. Systems Theory"},{"key":"1_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0022-0000(74)80034-6","volume":"9","author":"A. Gill","year":"1974","unstructured":"Gill, A., Kou, L.T.: Multiple-entry finite automata. J. Comput. System Sci.\u00a09, 1\u201319 (1974)","journal-title":"J. Comput. System Sci."},{"issue":"3","key":"1_CR9","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/321127.321132","volume":"9","author":"S. Ginsburg","year":"1962","unstructured":"Ginsburg, S., Rice, H.G.: Two families of languages related to ALGOL. J. ACM\u00a09(3), 350\u2013371 (1962)","journal-title":"J. ACM"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0020-0190(96)00095-6","volume":"59","author":"I. Glaister","year":"1996","unstructured":"Glaister, I., Shallit, J.: A lower bound technique for the size of nondeterministic finite automata. Inform. Process. Lett.\u00a059, 75\u201377 (1996)","journal-title":"Inform. Process. Lett."},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"37","author":"E.M. Gold","year":"1978","unstructured":"Gold, E.M.: Complexity of automaton identification from given data. Inform. Control\u00a037, 302\u2013320 (1978)","journal-title":"Inform. Control"},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0890-5401(90)90053-K","volume":"86","author":"J. Goldstine","year":"1990","unstructured":"Goldstine, J., Kintala, C.M.R., Wotschke, D.: On measuring nondeterminism in regular languages. Inform. Comput.\u00a086, 179\u2013194 (1990)","journal-title":"Inform. Comput."},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0890-5401(92)90014-7","volume":"100","author":"J. Goldstine","year":"1992","unstructured":"Goldstine, J., Leung, H., Wotschke, D.: On the relation between ambiguity and nondeterminism in finite automata. Inform. Comput.\u00a0100, 261\u2013270 (1992)","journal-title":"Inform. Comput."},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1016\/j.jcss.2005.04.001","volume":"71","author":"J. Goldstine","year":"2005","unstructured":"Goldstine, J., Leung, H., Wotschke, D.: Measuring nondeterminism in pushdown automata. J. Comput. System Sci.\u00a071, 440\u2013466 (2005)","journal-title":"J. Comput. System Sci."},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF01786988","volume":"15","author":"J. Goldstine","year":"1982","unstructured":"Goldstine, J., Price, J.K., Wotschke, D.: On reducing the number of states in a PDA. Math. Systems Theory\u00a015, 315\u2013321 (1982)","journal-title":"Math. Systems Theory"},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/BF01189852","volume":"26","author":"J. Goldstine","year":"1993","unstructured":"Goldstine, J., Price, J.K., Wotschke, D.: On reducing the number of stack symbols in a PDA. Math. Systems Theory\u00a026, 313\u2013326 (1993)","journal-title":"Math. Systems Theory"},{"key":"1_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/11779148_33","volume-title":"Developments in Language Theory","author":"H. Gruber","year":"2006","unstructured":"Gruber, H., Holzer, M.: Finding lower bounds for nondeterministic state complexity is hard (extended abstract). In: Ibarra, O.H., Dang, Z. (eds.) DLT 2006. LNCS, vol.\u00a04036, pp. 363\u2013374. Springer, Heidelberg (2006)"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Gruber, H., Holzer, M., Kutrib, M.: On measuring non-recursive trade-offs. In: Descriptional Complexity of Formal Systems (DCFS 2009), pp. 187\u2013198. Otto-von-Guericke-Universit\u00e4t Magdeburg (2009)","DOI":"10.4204\/EPTCS.3.13"},{"key":"1_CR19","volume-title":"Introduction to Formal Language Theory","author":"M.A. Harrison","year":"1978","unstructured":"Harrison, M.A.: Introduction to Formal Language Theory. Addison-Wesley, Reading (1978)"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"Hartmanis, J.: Context-free languages and Turing machine computations. In: Proc. Symposia in Applied Mathematics, vol.\u00a019, pp. 42\u201351 (1967)","DOI":"10.1090\/psapm\/019\/0235938"},{"key":"1_CR21","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1137\/0209010","volume":"9","author":"J. Hartmanis","year":"1980","unstructured":"Hartmanis, J.: On the succinctness of different representations of languages. SIAM J. Comput.\u00a09, 114\u2013120 (1980)","journal-title":"SIAM J. Comput."},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0304-3975(83)90016-6","volume":"26","author":"J. Hartmanis","year":"1983","unstructured":"Hartmanis, J.: On G\u00f6del speed-up and succinctness of language representations. Theoret. Comput. Sci.\u00a026, 335\u2013342 (1983)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR23","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0304-3975(96)00267-8","volume":"181","author":"C. Herzog","year":"1997","unstructured":"Herzog, C.: Pushdown automata with bounded nondeterminism and bounded ambiguity. Theoret. Comput. Sci.\u00a0181, 141\u2013157 (1997)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-642-00982-2_3","volume-title":"Language and Automata Theory and Applications","author":"M. Holzer","year":"2009","unstructured":"Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol.\u00a05457, pp. 23\u201342. Springer, Heidelberg (2009)"},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1142\/S0129054109006747","volume":"20","author":"M. Holzer","year":"2009","unstructured":"Holzer, M., Kutrib, M.: Nondeterministic finite automata - Recent results on the descriptional and computational complexity. Int. J. Found. Comput. Sci.\u00a020, 563\u2013580 (2009)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"Holzer, M., Kutrib, M.: Descriptional complexity \u2013 An introductory survey. In: Scientific Applications of Language Methods. Imperial College Press, London (to appear, 2010)","DOI":"10.1142\/9781848165458_0001"},{"key":"1_CR27","first-page":"453","volume":"6","author":"M. Holzer","year":"2001","unstructured":"Holzer, M., Salomaa, K., Yu, S.: On the state complexity of k-entry deterministic finite automata. J. Autom., Lang. Comb.\u00a06, 453\u2013466 (2001)","journal-title":"J. Autom., Lang. Comb."},{"key":"1_CR28","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/B978-0-12-417750-5.50022-1","volume-title":"The Theory of Machines and Computations","author":"J.E. Hopcroft","year":"1971","unstructured":"Hopcroft, J.E.: An nlogn algorithm for minimizing the state in a finite automaton. In: The Theory of Machines and Computations, pp. 189\u2013196. Academic Press, London (1971)"},{"key":"1_CR29","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)"},{"key":"1_CR30","unstructured":"Hromkovi\u010d, J., Schnitger, G.: Ambiguity and communication. In: Theoretical Aspects of Computer Science (STACS 2009), Dagstuhl, Germany. LIPICS, vol.\u00a03, pp. 107\u2013118 (2009)"},{"key":"1_CR31","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03442-2","volume-title":"Communication Complexity and Parallel Computing","author":"J. Hromkovi\u010d","year":"1997","unstructured":"Hromkovi\u010d, J.: Communication Complexity and Parallel Computing. Springer, Heidelberg (1997)"},{"key":"1_CR32","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1006\/inco.2001.3069","volume":"172","author":"J. Hromkovi\u010d","year":"2002","unstructured":"Hromkovi\u010d, J., Seibert, S., Karhum\u00e4ki, J., Klauck, H., Schnitger, G.: Communication complexity method for measuring nondeterminism in finite automata. Inform. Comput.\u00a0172, 202\u2013217 (2002)","journal-title":"Inform. Comput."},{"key":"1_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/3-540-16078-7_74","volume-title":"STACS 86","author":"O.H. Ibarra","year":"1986","unstructured":"Ibarra, O.H., Ravikumar, B.: On sparseness, ambiguity and other decision problems for acceptors and transducers. In: Monien, B., Vidal-Naquet, G. (eds.) STACS 1986. LNCS, vol.\u00a0210, pp. 171\u2013179. Springer, Heidelberg (1986)"},{"key":"1_CR34","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1142\/S012905419100011X","volume":"2","author":"T. Jiang","year":"1991","unstructured":"Jiang, T., McDowell, E., Ravikumar, B.: The structure and complexity of minimal NFA\u2019s over a unary alphabet. Int. J. Found. Comput. Sci.\u00a02, 163\u2013182 (1991)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"1_CR35","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1137\/0222067","volume":"22","author":"T. Jiang","year":"1993","unstructured":"Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. SIAM J. Comput.\u00a022, 1117\u20131141 (1993)","journal-title":"SIAM J. Comput."},{"key":"1_CR36","first-page":"269","volume":"5","author":"M. Kappes","year":"2000","unstructured":"Kappes, M.: Descriptional complexity of deterministic finite automata with multiple initial states. J. Autom., Lang. Comb.\u00a05, 269\u2013278 (2000)","journal-title":"J. Autom., Lang. Comb."},{"key":"1_CR37","doi-asserted-by":"crossref","unstructured":"Kintala, C.M.R.: Computations with a Restricted Number of Nondeterministic Steps. PhD thesis, Pennsylvania State University (1977)","DOI":"10.1145\/800105.803407"},{"key":"1_CR38","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF00263994","volume":"13","author":"C.M.R. Kintala","year":"1980","unstructured":"Kintala, C.M.R., Wotschke, D.: Amounts of nondeterminism in finite automata. Acta Inform.\u00a013, 199\u2013204 (1980)","journal-title":"Acta Inform."},{"key":"1_CR39","unstructured":"Kuich, W.: Finite automata and ambiguity. Report 253 of the IIG, Technische Universit\u00e4t Graz (1988)"},{"key":"1_CR40","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1142\/S0129054105003406","volume":"16","author":"M. Kutrib","year":"2005","unstructured":"Kutrib, M.: The phenomenon of non-recursive trade-offs. Int. J. Found. Comput. Sci.\u00a016, 957\u2013973 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"1_CR41","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.tcs.2007.01.015","volume":"376","author":"M. Kutrib","year":"2007","unstructured":"Kutrib, M., Malcher, A.: Context-dependent nondeterminism for pushdown automata. Theoret. Comput. Sci.\u00a0376, 101\u2013111 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR42","doi-asserted-by":"publisher","first-page":"3447","DOI":"10.1016\/j.tcs.2009.06.002","volume":"410","author":"M. Kutrib","year":"2009","unstructured":"Kutrib, M., Malcher, A., Werlein, L.: Regulated nondeterminism in pushdown automata. Theoret. Comput. Sci.\u00a0410, 3447\u20133460 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR43","first-page":"92","volume":"3","author":"E. Landau","year":"1903","unstructured":"Landau, E.: \u00dcber die Maximalordnung der Permutationen gegebenen Grades. Archiv der Math. und Phys.\u00a03, 92\u2013103 (1903)","journal-title":"Archiv der Math. und Phys."},{"key":"1_CR44","unstructured":"Landau, E.: Handbuch der Lehre von der Verteilung der Primzahlen. Teubner (1909)"},{"key":"1_CR45","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/S0304-3975(81)80005-9","volume":"13","author":"E.L. Leiss","year":"1981","unstructured":"Leiss, E.L.: Succinct representation of regular languages by Boolean automata. Theoret. Comput. Sci.\u00a013, 323\u2013330 (1981)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/11812128_19","volume-title":"Implementation and Application of Automata","author":"H. Leung","year":"2006","unstructured":"Leung, H.: Structurally unambiguous finite automata. In: Ibarra, O.H., Yen, H.-C. (eds.) CIAA 2006. LNCS, vol.\u00a04094, pp. 198\u2013207. Springer, Heidelberg (2006)"},{"key":"1_CR47","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/S0097539793252092","volume":"27","author":"H. Leung","year":"1998","unstructured":"Leung, H.: Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata. SIAM J. Comput.\u00a027, 1073\u20131082 (1998)","journal-title":"SIAM J. Comput."},{"key":"1_CR48","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1142\/S0129054105003418","volume":"16","author":"H. Leung","year":"2005","unstructured":"Leung, H.: Descriptional complexity of NFA of different ambiguity. Int. J. Found. Comput. Sci.\u00a016, 975\u2013984 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"1_CR49","first-page":"321","volume":"9","author":"O.B. Lupanov","year":"1963","unstructured":"Lupanov, O.B.: A comparison of two types of finite sources. Problemy Kybernetiki\u00a09, 321\u2013326 (1963) (in Russian); German translation: \u00dcber den Vergleich zweier Typen endlicher Quellen. Probleme der Kybernetik 6, 328\u2013335 (1966)","journal-title":"Problemy Kybernetiki"},{"key":"1_CR50","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/j.tcs.2004.03.070","volume":"327","author":"A. Malcher","year":"2004","unstructured":"Malcher, A.: Minimizing finite automata is computationally hard. Theoret. Comput. Sci.\u00a0327, 375\u2013390 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR51","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1109\/SWAT.1971.11","volume-title":"Symposium on Switching and Automata Theory (SWAT 1971)","author":"A.R. Meyer","year":"1971","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: Symposium on Switching and Automata Theory (SWAT 1971), pp. 188\u2013191. IEEE, Los Alamitos (1971)"},{"key":"1_CR52","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"20","author":"F.R. Moore","year":"1971","unstructured":"Moore, F.R.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Trans. Comput.\u00a020, 1211\u20131214 (1971)","journal-title":"IEEE Trans. Comput."},{"key":"1_CR53","doi-asserted-by":"crossref","unstructured":"Okhotin, A.: A study of unambiguous finite automata over a one-letter alphabet. TUCS Technical Report No 951, Turku Centre for Computer Science (2009)","DOI":"10.1007\/978-3-642-15155-2_49"},{"key":"1_CR54","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/978-3-540-70844-5_24","volume-title":"Implementation and Applications of Automata","author":"G. Pighizzini","year":"2008","unstructured":"Pighizzini, G.: Deterministic pushdown automata and unary languages. In: Ibarra, O.H., Ravikumar, B. (eds.) CIAA 2008. LNCS, vol.\u00a05148, pp. 232\u2013241. Springer, Heidelberg (2008)"},{"key":"1_CR55","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1006\/jcss.2002.1855","volume":"65","author":"G. Pighizzini","year":"2002","unstructured":"Pighizzini, G., Shallit, J., Wang, M.W.: Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds. J. Comput. System Sci.\u00a065, 393\u2013414 (2002)","journal-title":"J. Comput. System Sci."},{"key":"1_CR56","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M.O. Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev.\u00a03, 114\u2013125 (1959)","journal-title":"IBM J. Res. Dev."},{"key":"1_CR57","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1137\/0218083","volume":"18","author":"B. Ravikumar","year":"1989","unstructured":"Ravikumar, B., Ibarra, O.H.: Relating the type of ambiguity of finite automata to the succinctness of their representation. SIAM J. Comput.\u00a018, 1263\u20131282 (1989)","journal-title":"SIAM J. Comput."},{"key":"1_CR58","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-6264-0","volume-title":"Automata-theoretic Aspects of Formal Power Series","author":"A. Salomaa","year":"1978","unstructured":"Salomaa, A., Soittola, M.: Automata-theoretic Aspects of Formal Power Series. Springer, Heidelberg (1978)"},{"key":"1_CR59","first-page":"186","volume":"50","author":"K. Salomaa","year":"1993","unstructured":"Salomaa, K., Yu, S.: Limited nondeterminism for pushdown automata. Bull. EATCS\u00a050, 186\u2013193 (1993)","journal-title":"Bull. EATCS"},{"key":"1_CR60","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/S0022-0000(05)80054-6","volume":"49","author":"K. Salomaa","year":"1994","unstructured":"Salomaa, K., Yu, S.: Measures of nondeterminism for pushdown automata. J. Comput. System Sci.\u00a049, 362\u2013374 (1994)","journal-title":"J. Comput. System Sci."},{"key":"1_CR61","doi-asserted-by":"crossref","unstructured":"Schmidt, E.M.: Succinctness of Dscriptions of Context-Free, Regular and Finite Languages. PhD thesis, Cornell University, Ithaca, NY (1978)","DOI":"10.7146\/dpb.v7i84.6500"},{"key":"1_CR62","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1137\/0206039","volume":"6","author":"E.M. Schmidt","year":"1977","unstructured":"Schmidt, E.M., Szymanski, T.G.: Succinctness of descriptions of unambiguous context-free languages. SIAM J. Comput.\u00a06, 547\u2013553 (1977)","journal-title":"SIAM J. Comput."},{"key":"1_CR63","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-0000(80)90034-3","volume":"21","author":"M. Sipser","year":"1980","unstructured":"Sipser, M.: Lower bounds on the size of sweeping automata. J. Comput. System Sci.\u00a021, 195\u2013202 (1980)","journal-title":"J. Comput. System Sci."},{"key":"1_CR64","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/S0019-9958(67)90591-8","volume":"11","author":"R.E. Stearns","year":"1967","unstructured":"Stearns, R.E.: A regularity test for pushdown machines. Inform. Control\u00a011, 323\u2013340 (1967)","journal-title":"Inform. Control"},{"key":"1_CR65","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1137\/0214044","volume":"14","author":"R.E. Stearns","year":"1985","unstructured":"Stearns, R.E., Hunt III, H.B.: On the equivalence and containment problems for unambiguous regular expressions, regular grammars, and finite automata. SIAM J. Comput.\u00a014, 598\u2013611 (1985)","journal-title":"SIAM J. Comput."},{"key":"1_CR66","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321864.321865","volume":"22","author":"L.G. Valiant","year":"1975","unstructured":"Valiant, L.G.: Regularity and related problems for deterministic pushdown automata. J. ACM\u00a022, 1\u201310 (1975)","journal-title":"J. ACM"},{"key":"1_CR67","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0019-9958(76)90173-X","volume":"32","author":"L.G. Valiant","year":"1976","unstructured":"Valiant, L.G.: A note on the succinctness of descriptions of deterministic languages. Inform. Control\u00a032, 139\u2013145 (1976)","journal-title":"Inform. Control"},{"key":"1_CR68","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1016\/0022-0000(79)90038-2","volume":"18","author":"P.A.S. Veloso","year":"1979","unstructured":"Veloso, P.A.S., Gill, A.: Some remarks on multiple-entry finite automata. J. Comput. System Sci.\u00a018, 304\u2013306 (1979)","journal-title":"J. Comput. System Sci."},{"key":"1_CR69","first-page":"401","volume":"4","author":"D. Vermeir","year":"1981","unstructured":"Vermeir, D., Savitch, W.: On the amount of nondeterminism in pushdown automata. Fund. Inform.\u00a04, 401\u2013418 (1981)","journal-title":"Fund. Inform."},{"key":"1_CR70","unstructured":"Weber, A.: \u00dcber die Mehrdeutigkeit und Wertigkeit von endlichen Automaten und Transducern. Dissertation, Institut f\u00fcr Informatik, Johann Wolfgang Goethe-Universit\u00e4t Frankfurt am Main (1987) (in German)"},{"key":"1_CR71","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0304-3975(91)90381-B","volume":"88","author":"A. Weber","year":"1991","unstructured":"Weber, A., Seidl, H.: On the degree of ambiguity of finite automata. Theoret. Comput. Sci.\u00a088, 325\u2013349 (1991)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Reachability Problems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15349-5_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T21:21:47Z","timestamp":1740432107000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15349-5_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153488","9783642153495"],"references-count":71,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15349-5_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}