{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:53:00Z","timestamp":1725663180725},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540186250"},{"type":"electronic","value":"9783540480334"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1007\/3-540-18625-5_40","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T19:41:18Z","timestamp":1330198878000},"page":"26-43","source":"Crossref","is-referenced-by-count":0,"title":["Relating the degree of ambiguity of finite automata to the succinctness of their representation"],"prefix":"10.1007","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bala","family":"Ravikumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Berman, P., A note on sweeping automata, ICALP 1979, pp. 91\u201397.","DOI":"10.1007\/3-540-10003-2_62"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Chan, T. and O. Ibarra, On the finite-valuedness problem for sequential machines, Theoretical Computer Science, 1983, pp. 95\u2013101.","DOI":"10.1016\/0304-3975(88)90012-6"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Denes, J., K.H. Kim and F.W. Rouch, Automata on one symbol, Studies in Pure Mathematics 1985, pp. 127\u2013134.","DOI":"10.1007\/978-3-0348-5438-2_12"},{"key":"4_CR4","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/S0022-0000(76)80034-7","volume":"12","author":"A. Ehrenfeucht","year":"1976","unstructured":"Ehrenfeucht, A. and P. Zeiger, Complexity measures for regular expressions, Journal of Computer and System Sciences, 12, 1976, pp. 134\u2013146.","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR5","volume-title":"Automata, Languages and machines, Vol. A","author":"S. Eilenberg","year":"1974","unstructured":"Eilenberg, S., Automata, Languages and machines, Vol. A, Academic Press, NY 1974."},{"key":"4_CR6","unstructured":"Hopcroft J. and J. Ullman, Introduction to Automata Theory, Formal Languages and Computation, Addison-Wesley, 1979."},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Ibarra, O. and B. Ravikumar, On sparseness, ambiguity and other decision problems for acceptors and transducers, Third Annual Symposium on Theoretical Aspects of Computer Science, Orsay, France, 1986, pp. 171\u2013179.","DOI":"10.1007\/3-540-16078-7_74"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Kintala C. and D. Wotschke, Amounts of nondeterminism in finite automata, Acta Informatica, 1980, pp. 199\u2013204.","DOI":"10.1007\/BF00263994"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Kintala C. and D. Wotschke, Concurrent conciseness of degree, probabilistic, nondeterministic and deterministic finite automata, Fourth Symposium on Theoretical Aspects of Computer Science, 1986, pp. 291\u2013305.","DOI":"10.1007\/3-540-16078-7_84"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Kranakis, E., Primality and Cryptography, Yale University Technical Report, 1985.","DOI":"10.1007\/978-3-322-96647-6"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Kuich, W., On the entropy of context-free languages, Information and Control, 1970, pp. 173\u2013200.","DOI":"10.1016\/S0019-9958(70)90105-1"},{"key":"4_CR12","unstructured":"Mandl, R., Precise bounds associated with the subset construction on various classes of nondeterministic finite automata, Seventh Princeton Conference on Information and System Science, 1973, pp. 263\u2013267."},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Meyer, A. and M. Fischer, Economy of description by automata, grammars, and formal Systems, Proc. of Twelfth IEEE Symposium on Switching and Automata Theory, 1971, pp. 188\u2013191.","DOI":"10.1109\/SWAT.1971.11"},{"key":"4_CR14","doi-asserted-by":"crossref","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"20","author":"F. Moore","year":"1971","unstructured":"Moore, F., On the bounds for state-set size in the proofs of equivalence between nondeterministic and two-way automata, IEEE Transactions on Computers, 20, 1971, pp. 1211\u20131214.","journal-title":"IEEE Transactions on Computers"},{"key":"4_CR15","unstructured":"Paul, W., Kolmogorov complexity and lower bounds, 2nd International Conference on Fundamentals of Computation Theory, 1979."},{"key":"4_CR16","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M. Rabin","year":"1959","unstructured":"Rabin, M. and D. Scott, Finite automata and their decision problems, IBM Journal of Research and Development, 3, 1959, pp. 114\u2013125.","journal-title":"IBM Journal of Research and Development"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Sakoda, W. and M. Sipser, Nondeterminism and the size of two-way finite automata, Proceedings of Tenth Annual ACM Symposium on Theory of Computing, 1978, pp. 275\u2013286.","DOI":"10.1145\/800133.804357"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Schmidt, E., Succinctness of descriptions of context-free, regular and finite languages, Ph. D. Thesis, Cornell University, 1978.","DOI":"10.7146\/dpb.v7i84.6500"},{"key":"4_CR19","unstructured":"Schmidt, E., (private communication)."},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Sipser, M., Lower bounds on the size of sweeping automata, Proc. of Eleventh Annual ACM Symposium on Theory of Computing, 1979, pp. 360\u2013364.","DOI":"10.1145\/800135.804429"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"Sipser, M., Halting space-bounded computations, Theoretical Computer Science, 1980, pp. 335\u2013338.","DOI":"10.1016\/0304-3975(80)90053-5"},{"key":"4_CR22","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1137\/0214044","volume":"14","author":"R. Stearns","year":"1985","unstructured":"Stearns, R. and H. Hunt, On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata, SIAM Journal of Computing, 14, 1985, pp. 598\u2013611.","journal-title":"SIAM Journal of Computing"},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"Weber, A. and H. Seidl, On the degree of ambiguity of finite automata, Proc. of Math. Foundations of Comp. Science, 1986, pp. 620\u2013629.","DOI":"10.1007\/BFb0016289"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-18625-5_40.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:15:12Z","timestamp":1605644112000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-18625-5_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987]]},"ISBN":["9783540186250","9783540480334"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-18625-5_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1987]]}}}