{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:22:25Z","timestamp":1725495745261},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540677154"},{"type":"electronic","value":"9783540450221"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45022-x_17","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T23:57:25Z","timestamp":1194998245000},"page":"199-210","source":"Crossref","is-referenced-by-count":13,"title":["Measures of Nondeterminism in Finite Automata"],"prefix":"10.1007","author":[{"given":"Juraj","family":"Hromkovi\u010d","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juhani","family":"Karhum\u00e4ki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hartmut","family":"Klauck","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georg","family":"Schnitger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Seibert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,2,18]]},"reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0304-3975(96)00062-X","volume":"168","author":"M. Dietzfelbinger","year":"1996","unstructured":"M. Dietzfelbinger, J. Hromkovi\u010d, G. Schnitger. A comparison of two lower bound methods for communication complexity. Theoretical Computer Science, vol. 168, pp. 39\u201351, 1996.","journal-title":"Theoretical Computer Science"},{"key":"17_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BFb0023453","volume-title":"Symp. on Theoretical Aspects of Comp. Science","author":"P. Duri\u0161","year":"1997","unstructured":"P. Duri\u0161, J. Hromkovi\u010d, J.D.P. Rolim, G. Schnitger. Las Vegas Versus Determinism for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations. Symp. on Theoretical Aspects of Comp. Science, LNCS 1200, pp. 117\u2013128, 1997."},{"key":"17_CR3","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0890-5401(90)90053-K","volume":"86","author":"J. Goldstine","year":"1990","unstructured":"J. Goldstine, C.M.R. Kintala, D. Wotschke. On Measuring Nondeterminism in Regular Languages. Information and Comput., vol. 86, pp. 179\u2013194, 1990.","journal-title":"Information and Comput"},{"key":"17_CR4","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0890-5401(92)90014-7","volume":"100","author":"J. Goldstine","year":"1992","unstructured":"J. Goldstine, H. Leung, D. Wotschke. On the Relation between Ambiguity and Nondeterminism in Finite Automata. Information and Computation, vol. 100, pp. 261\u2013270, 1992.","journal-title":"Information and Computation"},{"key":"17_CR5","first-page":"311","volume":"48\u201349","author":"J. Hromkovi\u010d","year":"1986","unstructured":"J. Hromkovi\u010d. Relation between Chomsky Hierarchy and Communication Complexity Hier. Acta Math. Univ. Com., vol. 48\u201349, pp. 311\u2013317, 1986.","journal-title":"Acta Math. Univ. Com."},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d. Communication Complexity and Parallel Computing. Springer, 1997.","DOI":"10.1007\/978-3-662-03442-2"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d, G. Schnitger. Nondeterministic Communication with a Limited Number of Advice Bits. Proc. 28th ACM Symposium on Theory of Computation., pp. 451\u2013560, 1996.","DOI":"10.1145\/237814.238003"},{"key":"17_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BFb0023448","volume-title":"Symp. on Theoretical Aspects of Comp. Science","author":"J. Hromkovi\u010d","year":"1997","unstructured":"J. Hromkovi\u010d, S. Seibert, T. Wilke. Translating regular expressions into smalzl \u2208-free nondeterministic finite automata. Symp. on Theoretical Aspects of Comp. Science, LNCS 1200, pp. 55\u201366, 1997."},{"key":"17_CR9","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/S0022-0000(05)80049-2","volume":"49","author":"M. Karchmer","year":"1994","unstructured":"M. Karchmer, M. Saks, I. Newman, A. Wigderson. Non-deterministic Communication Complexity with few Witnesses. Journ. of Computer and System Sciences, vol. 49, pp. 247\u2013257, 1994.","journal-title":"Journ. of Computer and System Sciences"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"H. Klauck. Lower bounds for computation with limited Nondeterminism. 13th IEEE Conference on Computational Complexity, pp. 141\u2013153, 1998.","DOI":"10.1109\/CCC.1998.694600"},{"key":"17_CR11","unstructured":"H. Klauck. On automata with constant ambiguity. Manuscript."},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz, N. Nisan. Communication Complexity. Cambridge University Press, 1997.","DOI":"10.1017\/CBO9780511574948"},{"key":"17_CR13","unstructured":"L. Lovasz. Communication Complexity: A survey. in: Paths, Flows, and VLSI Layout, Springer 1990."},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, E. Schmidt. Las Vegas is better than determinism in VLSI and Distributed Computing. Proc. 14th ACM Symp. on Theory of Computing, pp. 330\u2013337, 1982.","DOI":"10.1145\/800070.802208"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"A.R. Meyer, M.J. Fischer. Economy of description by automata, grammars and formal systems, Proc. 12th Annual Symp. on Switching and automata theory, pp. 188\u2013191, 1971.","DOI":"10.1109\/SWAT.1971.11"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"S. Micali. Two-Way Deterministic Finite Automata are Exponentially More Succinct than Sweeping Automata, Information Proc. Letters, vol. 12, 1981.","DOI":"10.1016\/0020-0190(81)90012-0"},{"key":"17_CR17","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/0022-0000(84)90069-2","volume":"28","author":"C. Papadimitriou","year":"1984","unstructured":"C. Papadimitriou, M. Sipser. Communication Complexity. Journ. of Computer and System Sciences, vol. 28, pp. 260\u2013269, 1984.","journal-title":"Journ. of Computer and System Sciences"},{"issue":"2","key":"17_CR18","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-0000(80)90034-3","volume":"21","author":"M. Sipser","year":"1980","unstructured":"M. Sipser. Lower Bounds on the Size of Sweeping Automata. Journ. of Computer and System Sciences, vol. 21(2), pp. 195\u2013202, 1980.","journal-title":"Journ. of Computer and System Sciences"},{"key":"17_CR19","first-page":"223","volume":"43","author":"M. Yannakakis","year":"1991","unstructured":"M. Yannakakis. Expressing Combinatorial Optimization Problems by Linear Programs. Journ. of Comp. and System Sciences, vol. 43, pp. 223\u2013228, 1991.","journal-title":"Journ. of Comp. and System Sciences"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"A. Yao. Some Complexity Questions Related to Distributed Computing. Proc. 11th ACM Symp. on Theory of Computing, pp. 209\u2013213, 1979.","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45022-X_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T11:25:37Z","timestamp":1556969137000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45022-X_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540677154","9783540450221"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-45022-x_17","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}