{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T13:36:24Z","timestamp":1725888984326},"publisher-location":"Cham","reference-count":14,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319602516"},{"type":"electronic","value":"9783319602523"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-60252-3_14","type":"book-chapter","created":{"date-parts":[[2017,6,2]],"date-time":"2017-06-02T14:59:13Z","timestamp":1496415553000},"page":"177-188","source":"Crossref","is-referenced-by-count":0,"title":["One-Time Nondeterministic Computations"],"prefix":"10.1007","author":[{"given":"Markus","family":"Holzer","sequence":"first","affiliation":[]},{"given":"Martin","family":"Kutrib","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,3]]},"reference":[{"issue":"2","key":"14_CR1","first-page":"193","volume":"8","author":"J Goldstine","year":"2002","unstructured":"Goldstine, J., Kappes, M., Kintala, C.M.R., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. J. Univ. Comput. Sci. 8(2), 193\u2013234 (2002)","journal-title":"J. Univ. Comput. Sci."},{"key":"14_CR2","volume-title":"Introduction to Formal Language Theory","author":"MA Harrison","year":"1978","unstructured":"Harrison, M.A.: Introduction to Formal Language Theory. Addison-Wesley, Reading (1978)"},{"key":"14_CR3","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1090\/psapm\/019\/0235938","volume":"19","author":"J Hartmanis","year":"1967","unstructured":"Hartmanis, J.: Context-free languages and turing machine computations. Proc. Symp. Appl. Math. 19, 42\u201351 (1967)","journal-title":"Proc. Symp. Appl. Math."},{"key":"14_CR4","doi-asserted-by":"crossref","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. 26, 335\u2013342 (1983)","journal-title":"Theoret. Comput. Sci."},{"key":"14_CR5","first-page":"101","volume":"38","author":"J Hartmanis","year":"1989","unstructured":"Hartmanis, J.: G\u00f6del, von Neumann and the P\n            $$=?$$\n           NP problem. Bull. EATCS 38, 101\u2013107 (1989)","journal-title":"Bull. EATCS"},{"key":"14_CR6","unstructured":"Hartmanis, J., Hunt III., H.B.: The LBA problem and its importance in the theory of computing. In: Complexity of Computing, SIAM AMS Proceedings, vol. 7, pp. 1\u201326 (1974)"},{"key":"14_CR7","doi-asserted-by":"crossref","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. 181, 141\u2013157 (1997)","journal-title":"Theoret. Comput. Sci."},{"key":"14_CR8","unstructured":"Herzog, C.: Die Rolle des Nichtdeterminismus in kontextfreien Sprachen. Doctoral dissertation, Universit\u00e4t Frankfurt (1999). (in German)"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Holzer, M., Kutrib, M.: Descriptional complexity - an introductory survey. In: Scientific Applications of Language Methods, pp. 1\u201358. Imperial College Press (2010)","DOI":"10.1142\/9781848165458_0001"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.: Automata theory: its past and future. In: Yu, S. (ed.) A Half-Century of Automata Theory, pp. 37\u201347. World Scientific (2001)","DOI":"10.1142\/9789812810168_0003"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: Proceedings of the 12th Annual Symposium on Switching and Automata Theory, pp. 188\u2013191. IEEE Computer Society Press (1971)","DOI":"10.1109\/SWAT.1971.11"},{"key":"14_CR12","doi-asserted-by":"crossref","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"20","author":"FR 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. 20, 1211\u20131219 (1971)","journal-title":"IEEE Trans. Comput."},{"key":"14_CR13","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"MO Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3, 114\u2013125 (1959)","journal-title":"IBM J. Res. Dev."},{"key":"14_CR14","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0304-3975(92)00011-F","volume":"125","author":"S Yu","year":"1994","unstructured":"Yu, S., Zhuang, Q., Salomaa, K.: The state complexity of some basic operations on regular languages. Theoret. Comput. Sci. 125, 315\u2013328 (1994)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-60252-3_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,2]],"date-time":"2017-06-02T15:02:27Z","timestamp":1496415747000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-60252-3_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319602516","9783319602523"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-60252-3_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}