{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T12:35:08Z","timestamp":1649075708314},"reference-count":19,"publisher":"EDP Sciences","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2005,4]]},"DOI":"10.1051\/ita:2005024","type":"journal-article","created":{"date-parts":[[2005,4,20]],"date-time":"2005-04-20T12:49:59Z","timestamp":1114001399000},"page":"391-401","source":"Crossref","is-referenced-by-count":0,"title":["Complexity results for prefix grammars"],"prefix":"10.1051","volume":"39","author":[{"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[]},{"given":"Holger","family":"Petersen","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2005,4,15]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF01969548","volume":"6","author":"B\u00fcchi","year":"1964","journal-title":"Archiv Math. Logik und Grundlagenforschung"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"J.R. B\u00fcchi,Finite Automata, their Algebras and Grammars. Springer, Berlin-Heidelberg-New York (1989).","DOI":"10.1007\/978-1-4613-8853-1"},{"key":"R3","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF01705888","volume":"4","author":"B\u00fcchi","year":"1970","journal-title":"Math. Syst. Theor."},{"key":"R4","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0304-3975(92)90278-N","volume":"106","author":"Caucal","year":"1992","journal-title":"Theor. Comput. Sci."},{"key":"R5","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"Chandra","year":"2981","journal-title":"J. Association Computing Machinery"},{"key":"R6","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/10722167_20","volume":"1855","author":"Esparza","year":"2000","journal-title":"Lect. Notes Comput. Sci."},{"key":"R7","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/S0890-5401(03)00139-1","volume":"186","author":"Esparza","year":"2003","journal-title":"Inform. Comput."},{"key":"R8","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0020-0190(94)00074-3","volume":"51","author":"Frazier","year":"1994","journal-title":"Inform. Process. Lett."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"S.A. Greibach, A note on pushdown store automata and regular systems, inProc. of the AMS18(1967) 263\u2013268.","DOI":"10.1090\/S0002-9939-1967-0209086-1"},{"key":"R10","unstructured":"J.E. Hopcroft and R.M. Karp,A linear algorithm for testing the equivalence of finite automata. Report TR 71-114, Department of Computer Science, Cornell University (1971)."},{"key":"R11","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"Jones","year":"1977","journal-title":"Theor. Comput. Sci."},{"key":"R12","first-page":"41","volume":"17","author":"Kratko","year":"1966","journal-title":"Problemy Kibernet."},{"key":"R13","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/0213010","volume":"13","author":"Ladner","year":"1984","journal-title":"SIAM J. Comput."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"A.R. Meyer and L.J. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space, inProc. of the 13th Annual IEEE Symposium on Switching and Automata Theory, College Park (Maryland) (1972) 125\u2013129.","DOI":"10.1109\/SWAT.1972.29"},{"key":"R15","unstructured":"C.H. Papadimitriou,Computational Complexity. Addison Wesley (1994)."},{"key":"R16","first-page":"245","volume":"5","author":"Petersen","year":"2000","journal-title":"J. Autom. Lang. Comb."},{"key":"R17","unstructured":"B. Ravikumar and L. Quan,Efficient algorithms for prefix grammars.Available at http:\/\/www.cs.sonoma.edu\/~ravi (2002)."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"L.J. Stockmeyer and A.R. Meyer, Word problems requiring exponential time, inProc. of the 5th ACM Symposium on Theory of Computing (STOC'73), Austin (Texas) (1973) 1\u20139.","DOI":"10.1145\/800125.804029"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"H. Straubing,Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user (1994).","DOI":"10.1007\/978-1-4612-0289-9"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita:2005024\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T00:58:02Z","timestamp":1586221082000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita:2005024"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,4]]},"references-count":19,"journal-issue":{"issue":"2"},"alternative-id":["ita0433"],"URL":"https:\/\/doi.org\/10.1051\/ita:2005024","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,4]]}}}