Abstract
We consider the problem of determining if a string w belongs to a language L specified by an automaton (NFA, or PDA augmented by reversal-bounded counters, etc.) where the string w is specified by its Parikh vector. If the automaton (PDA augmented with reversal-bounded counters) is fixed and the Parikh vector is encoded in unary (binary), the problem is in DLOGSPACE (PTIME). When the automaton is part of the input and the Parikh vector is encoded in binary, we show the following results: if the input is an NFA accepting a letter-bounded language (i.e., \(\subseteq a_1^* \cdots a_k^*\) for some distinct symbols a 1, ..., a k ), the problem is in PTIME, but if the input is an NFA accepting a word-bounded language (i.e., \(\subseteq w_1^* \cdots w_m^*\) for some nonnull strings w 1, ..., w m ), it is NP-complete. The proofs involve solving systems of linear Diophantine equations with non-negative integer coefficients. As an application of the results, we present efficient algorithms for a generalization of a tiling problem posed recently by Dana Scott. Finally, we give a classification of the complexity of the membership problem for restricted classes of semilinear sets.
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
Baker, B.S., Book, R.V.: Reversal-bounded multipushdown machines. J. Comput. Syst. Sci. 8(3), 315–332 (1974)
Esparza, J.: Petri nets, commutative context-free grammars and basic parallel processes. Fundamenta Informaticae 30, 23–41 (1997)
Ginsburg, S.: The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York (1966)
Golomb, S.W.: Polyominoes, 2nd edn. Princeton University Press (1994) ISBN 0-691-02444-8
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata, Languages and Computation. Addison-Wesley (1978)
Hyunh, T.-D.: The Complexity of semilinear sets. Elektr. Inform.-verarbeitung and Kybern. 6, 291–338 (1982)
Hyunh, T.-D.: Commutative Grammars: The Complexity of Uniform Word Problems. Information and Control 57, 21–39 (1983)
Ibarra, O.H.: Reversal-bounded multicounter machines and their decision problems. J. Assoc. Comput. Mach. 25, 116–133 (1978)
Ibarra, O.H., Ravikumar, B.: On sparseness and ambiguity for acceptors and transducers. In: Monien, B., Vidal-Naquet, G. (eds.) STACS 1986. LNCS, vol. 210, pp. 171–179. Springer, Heidelberg (1985)
Ibarra, O.H., Ravikumar, B.: On bounded languages and reversal-bounded automata. In: Dediu, A.-H., Martín-Vide, C., Truthe, B. (eds.) LATA 2013. LNCS, vol. 7810, pp. 359–370. Springer, Heidelberg (2013)
Ibarra, O.H., Seki, S.: Characterizations of bounded semilinear languages by one-way and two-way deterministic machines. IJFCS 23, 1291–1306 (2012)
Ibarra, O.H., Yen, H.: On the Containment and Equivalence Problems for Two-way Transducers. Theoretical Computer Science 429, 155–163 (2012)
Kopczynski, E., To, A.W.: Parikh Images of Grammars: Complexity and Applications. In: Proc. of 25th Annual IEEE Logic in Computer Science, pp. 80–89 (2010)
Lavado, G.J., Pighizzini, G., Seki, S.: Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol. 7410, pp. 284–295. Springer, Heidelberg (2012)
Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press (2001)
Lenstra Jr., H.W.: Integer programming with a fixed number of variables. Mathematics of Operations Research 8, 583–548 (1983)
Lueker, G.S.: Two NP-Complete Problems in Nonnegative Integer Programming. Report No. 178, Computer Science Laboratory, Princeton University (1975)
Parikh, R.J.: On context-free languages. J. Assoc. Comput. Mach. 13, 570–581 (1966)
Scott, D.S.: Programming a combinatorial puzzle. Technical Report No. 1, Department of Electrical Engineering. Princeton University (1958)
To, A.W.: Parikh Images of Regular Languages: Complexity and Applications (2010) (unpublished manuscript)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Ibarra, O.H., Ravikumar, B. (2014). On the Parikh Membership Problem for FAs, PDAs, and CMs. In: Dediu, AH., Martín-Vide, C., Sierra-Rodríguez, JL., Truthe, B. (eds) Language and Automata Theory and Applications. LATA 2014. Lecture Notes in Computer Science, vol 8370. Springer, Cham. https://doi.org/10.1007/978-3-319-04921-2_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-04921-2_2
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04920-5
Online ISBN: 978-3-319-04921-2
eBook Packages: Computer ScienceComputer Science (R0)