{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:41:54Z","timestamp":1725795714353},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439500"},{"type":"electronic","value":"9783662439517"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43951-7_13","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T08:37:49Z","timestamp":1402475869000},"page":"146-157","source":"Crossref","is-referenced-by-count":2,"title":["Unary Pushdown Automata and Straight-Line Programs"],"prefix":"10.1007","author":[{"given":"Dmitry","family":"Chistikov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rupak","family":"Majumdar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"13_CR1","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1006\/jcss.2002.1852","volume":"65","author":"P. Berman","year":"2002","unstructured":"Berman, P., Karpinski, M., Larmore, L.L., Plandowski, W., Rytter, W.: On the complexity of pattern matching for highly compressed two-dimensional texts. JCSS\u00a065(2), 332\u2013350 (2002)","journal-title":"JCSS"},{"issue":"1","key":"13_CR2","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0304-3975(98)00255-2","volume":"218","author":"J. Berstel","year":"1999","unstructured":"Berstel, J., Boasson, L.: Partial words and a theorem of Fine and Wilf. TCS\u00a0218(1), 135\u2013141 (1999)","journal-title":"TCS"},{"key":"13_CR3","series-title":"IFIP","first-page":"87","volume-title":"IFIP TCS 2008","author":"A. Bertoni","year":"2008","unstructured":"Bertoni, A., Choffrut, C., Radicioni, R.: Literal shuffle of compressed words. In: Ausiello, G., Karhum\u00e4ki, J., Mauri, G., Ong, L. (eds.) IFIP TCS 2008. IFIP, vol.\u00a0273, pp. 87\u2013100. Springer, Boston (2008)"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"B\u00f6hm, S., G\u00f6ller, S., Jan\u010dar, P.: Equivalence of deterministic one-counter automata is NL-complete. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) STOC\u201913, pp. 131\u2013140. ACM (2013)","DOI":"10.1145\/2488608.2488626"},{"issue":"2","key":"13_CR5","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1006\/jcss.1998.1588","volume":"57","author":"H. Caussinus","year":"1998","unstructured":"Caussinus, H., McKenzie, P., Th\u00e9rien, D., Vollmer, H.: Nondeterministic NC 1 computation. JCSS\u00a057(2), 200\u2013212 (1998)","journal-title":"JCSS"},{"key":"13_CR6","unstructured":"Fischer, M.J., Paterson, M.S.: String-matching and other products. In: Karp, R. (ed.) SIAM-AMS Proceedings, vol.\u00a07. AMS (1974)"},{"issue":"3","key":"13_CR7","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. Journal of the ACM\u00a09(3), 350\u2013371 (1962)","journal-title":"Journal of the ACM"},{"issue":"1","key":"13_CR8","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/s00224-008-9144-8","volume":"46","author":"C. Gla\u00dfer","year":"2010","unstructured":"Gla\u00dfer, C., Herr, K., Reitwie\u00dfner, C., Travers, S., Waldherr, M.: Equivalence problems for circuits over sets of natural numbers. Theory of Computing Systems\u00a046(1), 80\u2013103 (2010)","journal-title":"Theory of Computing Systems"},{"issue":"3","key":"13_CR9","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/BF00289308","volume":"16","author":"L.M. Goldschlager","year":"1981","unstructured":"Goldschlager, L.M.: \u03b5-productions in context-free grammars. Acta Informatica\u00a016(3), 303\u2013308 (1981)","journal-title":"Acta Informatica"},{"issue":"1","key":"13_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(89)90023-7","volume":"43","author":"E. Gr\u00e4del","year":"1989","unstructured":"Gr\u00e4del, E.: Dominoes and the complexity of subclasses of logical theories. Annals of Pure and Applied Logic\u00a043(1), 1\u201330 (1989)","journal-title":"Annals of Pure and Applied Logic"},{"issue":"3","key":"13_CR11","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0304-3975(88)90136-3","volume":"56","author":"E. Gr\u00e4del","year":"1988","unstructured":"Gr\u00e4del, E.: Subclasses of Presburger arithmetic and the polynomial-time hierarchy. TCS\u00a056(3), 289\u2013301 (1988)","journal-title":"TCS"},{"issue":"2","key":"13_CR12","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/S0022-0000(76)80038-4","volume":"12","author":"H.B. Hunt III","year":"1976","unstructured":"Hunt III, H.B., Rosenkrantz, D.J., Szymanski, T.G.: On the equivalence, containment, and covering problems for the regular and context-free languages. JCSS\u00a012(2), 222\u2013268 (1976)","journal-title":"JCSS"},{"key":"13_CR13","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0019-9958(83)80022-9","volume":"57","author":"D.T. Huynh","year":"1983","unstructured":"Huynh, D.T.: Commutative grammars: the complexity of uniform word problems. Information and Control\u00a057, 21\u201339 (1983)","journal-title":"Information and Control"},{"issue":"2\u20133","key":"13_CR14","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0304-3975(84)90092-6","volume":"33","author":"D.T. Huynh","year":"1984","unstructured":"Huynh, D.T.: Deciding the inequivalence of context-free grammars with 1-letter terminal alphabet is $\\Sigma_2^p$ -complete. TCS\u00a033(2\u20133), 305\u2013326 (1984)","journal-title":"TCS"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Jan\u010dar, P.: Decidability of DPDA language equivalence via first-order grammars. In: LICS\u00a02012, pp. 415\u2013424. IEEE (2012)","DOI":"10.1109\/LICS.2012.51"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Je\u017c, A.: The complexity of compressed membership problems for finite automata. Theory of Computing Systems, 1\u201334 (2013)","DOI":"10.1007\/s00224-013-9443-6"},{"issue":"2","key":"13_CR17","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N.D. Jones","year":"1976","unstructured":"Jones, N.D., Laaser, W.T.: Complete problems for deterministic polynomial time. TCS\u00a03(2), 105\u2013117 (1976)","journal-title":"TCS"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Kopczy\u0144ski, E., To, A.W.: Parikh images of grammars: complexity and applications. In: LICS\u00a02010, pp. 80\u201389. IEEE Computer Society (2010)","DOI":"10.1109\/LICS.2010.21"},{"key":"13_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/11821069_59","volume-title":"Mathematical Foundations of Computer Science 2006","author":"Y. Lifshits","year":"2006","unstructured":"Lifshits, Y., Lohrey, M.: Querying and embedding compressed texts. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 681\u2013692. Springer, Heidelberg (2006)"},{"issue":"2","key":"13_CR20","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1515\/gcc-2012-0016","volume":"4","author":"M. Lohrey","year":"2012","unstructured":"Lohrey, M.: Algorithmics on SLP-compressed strings: a survey. Groups Complexity Cryptology\u00a04(2), 241\u2013299 (2012)","journal-title":"Groups Complexity Cryptology"},{"issue":"6","key":"13_CR21","doi-asserted-by":"publisher","first-page":"951","DOI":"10.1016\/j.ic.2011.01.009","volume":"209","author":"M. Lohrey","year":"2011","unstructured":"Lohrey, M.: Leaf languages and string compression. Information and Computation\u00a0209(6), 951\u2013965 (2011)","journal-title":"Information and Computation"},{"issue":"5","key":"13_CR22","doi-asserted-by":"publisher","first-page":"1210","DOI":"10.1137\/S0097539704445950","volume":"35","author":"M. Lohrey","year":"2006","unstructured":"Lohrey, M.: Word problems and membership problems on compressed words. SIAM Journal on Computing\u00a035(5), 1210\u20131240 (2006)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"13_CR23","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s00037-007-0229-6","volume":"16","author":"P. McKenzie","year":"2007","unstructured":"McKenzie, P., Wagner, K.W.: The complexity of membership problems for circuits over sets of natural numbers. Computational Complexity\u00a016(3), 211\u2013244 (2007)","journal-title":"Computational Complexity"},{"issue":"4","key":"13_CR24","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1142\/S0129054109006784","volume":"20","author":"G. Pighizzini","year":"2009","unstructured":"Pighizzini, G.: Deterministic pushdown automata and unary languages. International Journal of Foundations of Computer Science\u00a020(4), 629\u2013645 (2009)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"13_CR25","doi-asserted-by":"crossref","unstructured":"Plandowski, W., Rytter, W.: Complexity of language recognition problems for compressed words. In: Karhum\u00e4ki, J., Maurer, H., P\u0103un, G., Rozenberg, G. (eds.) Jewels are Forever, pp. 262\u2013272. Springer (1999)","DOI":"10.1007\/978-3-642-60207-8_23"},{"key":"13_CR26","unstructured":"Schmidt-Schau\u00df, M.: Matching of compressed patterns with character variables. In: Tiwari, A. (ed.) RTA 2012. LIPIcs, vol.\u00a015, pp. 272\u2013287. Dagstuhl (2012)"},{"issue":"4","key":"13_CR27","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/BF02679468","volume":"30","author":"U. Sch\u00f6ning","year":"1997","unstructured":"Sch\u00f6ning, U.: Complexity of Presburger arithmetic with fixed quantifier dimension. Theory of Computing Systems\u00a030(4), 423\u2013428 (1997)","journal-title":"Theory of Computing Systems"},{"issue":"1-2","key":"13_CR28","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1016\/S0304-3975(02)00027-0","volume":"281","author":"G. S\u00e9nizergues","year":"2002","unstructured":"S\u00e9nizergues, G.: L(A)\u2009=\u2009L(B)? A simplified decidability proof. TCS\u00a0281(1-2), 555\u2013608 (2002)","journal-title":"TCS"},{"key":"13_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1007\/3-540-45465-9_70","volume-title":"Automata, Languages and Programming","author":"C. Stirling","year":"2002","unstructured":"Stirling, C.: Deciding DPDA equivalence is primitive recursive. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, L., Conejo, R., Hennessy, M. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 821\u2013832. Springer, Heidelberg (2002)"},{"key":"13_CR30","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: Preliminary report. In: STOC\u00a01973, pp. 1\u20139. ACM (1973)","DOI":"10.1145\/800125.804029"},{"key":"13_CR31","unstructured":"Valiant, L.: Decision procedures for families of deterministic pushdown automata. PhD thesis. University of Warwick (1973)"},{"key":"13_CR32","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/11532231_25","volume-title":"Automated Deduction \u2013 CADE-20","author":"K.N. Verma","year":"2005","unstructured":"Verma, K.N., Seidl, H., Schwentick, T.: On the complexity of equational Horn clauses. In: Nieuwenhuis, R. (ed.) CADE 2005. LNCS (LNAI), vol.\u00a03632, pp. 337\u2013352. Springer, Heidelberg (2005)"},{"key":"13_CR33","doi-asserted-by":"crossref","unstructured":"Von zur Gathen, J., Sieveking, M.: A bound on solutions of linear integer equalities and inequalities. Proceedings of the AMS 72(1), 155\u2013158 (1978)","DOI":"10.1090\/S0002-9939-1978-0500555-0"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43951-7_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,11]],"date-time":"2019-08-11T12:21:09Z","timestamp":1565526069000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43951-7_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439500","9783662439517"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43951-7_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}