Abstract
We consider decision problems for deterministic pushdown automata over the unary alphabet (udpda, for short). Udpda are a simple computation model that accept exactly the unary regular languages, but can be exponentially more succinct than finite-state automata. We complete the complexity landscape for udpda by showing that emptiness (and thus universality) is P-hard, equivalence and compressed membership problems are P-complete, and inclusion is coNP-complete. Our upper bounds are based on a translation theorem between udpda and straight-line programs over the binary alphabet (SLPs). We show that the characteristic sequence of any udpda can be represented as a pair of SLPs—one for the prefix, one for the lasso—that have size linear in the size of the udpda and can be computed in polynomial time. Hence, decision problems on udpda are reduced to decision problems on SLPs. Conversely, any SLP can be converted in logarithmic space into a udpda, and this forms the basis for our lower bound proofs. We show coNP-hardness of the ordered matching problem for SLPs, from which we derive coNP-hardness for inclusion. In addition, we complete the complexity landscape for unary nondeterministic pushdown automata by showing that the universality problem is Π2 P-hard, using a new class of integer expressions. Our techniques have applications beyond udpda. We show that our results imply Π2 P-completeness for a natural fragment of Presburger arithmetic and coNP lower bounds for compressed matching problems with one-character wildcards.
The full version of the paper is available at http://arxiv.org/abs/1403.0509 .
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Berman, P., Karpinski, M., Larmore, L.L., Plandowski, W., Rytter, W.: On the complexity of pattern matching for highly compressed two-dimensional texts. JCSS 65(2), 332–350 (2002)
Berstel, J., Boasson, L.: Partial words and a theorem of Fine and Wilf. TCS 218(1), 135–141 (1999)
Bertoni, A., Choffrut, C., Radicioni, R.: Literal shuffle of compressed words. In: Ausiello, G., Karhumäki, J., Mauri, G., Ong, L. (eds.) IFIP TCS 2008. IFIP, vol. 273, pp. 87–100. Springer, Boston (2008)
Böhm, S., Göller, S., Jančar, P.: Equivalence of deterministic one-counter automata is NL-complete. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) STOC’13, pp. 131–140. ACM (2013)
Caussinus, H., McKenzie, P., Thérien, D., Vollmer, H.: Nondeterministic NC 1 computation. JCSS 57(2), 200–212 (1998)
Fischer, M.J., Paterson, M.S.: String-matching and other products. In: Karp, R. (ed.) SIAM-AMS Proceedings, vol. 7. AMS (1974)
Ginsburg, S., Rice, H.G.: Two families of languages related to ALGOL. Journal of the ACM 9(3), 350–371 (1962)
Glaßer, C., Herr, K., Reitwießner, C., Travers, S., Waldherr, M.: Equivalence problems for circuits over sets of natural numbers. Theory of Computing Systems 46(1), 80–103 (2010)
Goldschlager, L.M.: ε-productions in context-free grammars. Acta Informatica 16(3), 303–308 (1981)
Grädel, E.: Dominoes and the complexity of subclasses of logical theories. Annals of Pure and Applied Logic 43(1), 1–30 (1989)
Grädel, E.: Subclasses of Presburger arithmetic and the polynomial-time hierarchy. TCS 56(3), 289–301 (1988)
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 12(2), 222–268 (1976)
Huynh, D.T.: Commutative grammars: the complexity of uniform word problems. Information and Control 57, 21–39 (1983)
Huynh, D.T.: Deciding the inequivalence of context-free grammars with 1-letter terminal alphabet is \(\Sigma_2^p\)-complete. TCS 33(2–3), 305–326 (1984)
Jančar, P.: Decidability of DPDA language equivalence via first-order grammars. In: LICS 2012, pp. 415–424. IEEE (2012)
Jeż, A.: The complexity of compressed membership problems for finite automata. Theory of Computing Systems, 1–34 (2013)
Jones, N.D., Laaser, W.T.: Complete problems for deterministic polynomial time. TCS 3(2), 105–117 (1976)
Kopczyński, E., To, A.W.: Parikh images of grammars: complexity and applications. In: LICS 2010, pp. 80–89. IEEE Computer Society (2010)
Lifshits, Y., Lohrey, M.: Querying and embedding compressed texts. In: Královič, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 681–692. Springer, Heidelberg (2006)
Lohrey, M.: Algorithmics on SLP-compressed strings: a survey. Groups Complexity Cryptology 4(2), 241–299 (2012)
Lohrey, M.: Leaf languages and string compression. Information and Computation 209(6), 951–965 (2011)
Lohrey, M.: Word problems and membership problems on compressed words. SIAM Journal on Computing 35(5), 1210–1240 (2006)
McKenzie, P., Wagner, K.W.: The complexity of membership problems for circuits over sets of natural numbers. Computational Complexity 16(3), 211–244 (2007)
Pighizzini, G.: Deterministic pushdown automata and unary languages. International Journal of Foundations of Computer Science 20(4), 629–645 (2009)
Plandowski, W., Rytter, W.: Complexity of language recognition problems for compressed words. In: Karhumäki, J., Maurer, H., Păun, G., Rozenberg, G. (eds.) Jewels are Forever, pp. 262–272. Springer (1999)
Schmidt-Schauß, M.: Matching of compressed patterns with character variables. In: Tiwari, A. (ed.) RTA 2012. LIPIcs, vol. 15, pp. 272–287. Dagstuhl (2012)
Schöning, U.: Complexity of Presburger arithmetic with fixed quantifier dimension. Theory of Computing Systems 30(4), 423–428 (1997)
Sénizergues, G.: L(A) = L(B)? A simplified decidability proof. TCS 281(1-2), 555–608 (2002)
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. 2380, pp. 821–832. Springer, Heidelberg (2002)
Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: Preliminary report. In: STOC 1973, pp. 1–9. ACM (1973)
Valiant, L.: Decision procedures for families of deterministic pushdown automata. PhD thesis. University of Warwick (1973)
Verma, K.N., Seidl, H., Schwentick, T.: On the complexity of equational Horn clauses. In: Nieuwenhuis, R. (ed.) CADE 2005. LNCS (LNAI), vol. 3632, pp. 337–352. Springer, Heidelberg (2005)
Von zur Gathen, J., Sieveking, M.: A bound on solutions of linear integer equalities and inequalities. Proceedings of the AMS 72(1), 155–158 (1978)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chistikov, D., Majumdar, R. (2014). Unary Pushdown Automata and Straight-Line Programs. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds) Automata, Languages, and Programming. ICALP 2014. Lecture Notes in Computer Science, vol 8573. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43951-7_13
Download citation
DOI: https://doi.org/10.1007/978-3-662-43951-7_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43950-0
Online ISBN: 978-3-662-43951-7
eBook Packages: Computer ScienceComputer Science (R0)