Document Open Access Logo

The Complexity of Downward Closure Comparisons

Author Georg Zetzsche

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.123.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Georg Zetzsche

Cite As Get BibTex

Georg Zetzsche. The Complexity of Downward Closure Comparisons. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 123:1-123:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.123

Abstract

The downward closure of a language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of every language is regular. Moreover, recent results show that downward closures are computable for quite powerful system models.

One advantage of abstracting a language by its downward closure is that then equivalence and inclusion become decidable. In this work, we study the complexity of these two problems. More precisely, we consider the following decision problems: Given languages K and L from classes C and D, respectively, does the downward closure of K include (equal) that of L?

These problems are investigated for finite automata, one-counter automata, context-free grammars, and reversal-bounded counter automata. For each combination, we prove a completeness result either for fixed or for arbitrary alphabets. Moreover, for Petri net languages, we show that both problems are Ackermann-hard and for higher-order pushdown automata of order k, we prove hardness for complements of nondeterministic k-fold exponential time.

Subject Classification

Keywords
  • Downward closures
  • Complexity
  • Inclusion
  • Equivalence

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P. A. Abdulla, L. Boasson, and A. Bouajjani. Effective lossy queue languages. In ICALP 2001, 2001. Google Scholar
  2. P. A. Abdulla, A. Collomb-Annichini, A. Bouajjani, and B. Jonsson. Using forward reachability analysis for verification of lossy channel systems. Formal Methods in System Design, 25(1):39-65, 2004. Google Scholar
  3. M. F. Atig, D. Chistikov, P. Hofman, K. N. Kumar, P. Saivasan, and G. Zetzsche. The complexity of regular abstractions of one-counter languages. To appear in LICS 2016. Google Scholar
  4. G. Bachmeier, M. Luttenberger, and M. Schlund. Finite automata for the sub- and superword closure of cfls: Descriptional and computational complexity. In LATA 2015, 2015. Google Scholar
  5. B. S. Baker and R. V. Book. Reversal-bounded multipushdown machines. Journal of Computer and System Sciences, 8(3):315-332, 1974. Google Scholar
  6. P. Berman, M. Karpinski, L. L. Larmore, W. Plandowski, and W. Rytter. On the complexity of pattern matching for highly compressed two-dimensional texts. In CPM 1997, 1997. Google Scholar
  7. B. Courcelle. On constructing obstruction sets of words. Bulletin of the EATCS, 44:178-186, 1991. Google Scholar
  8. W. Damm and A. Goerdt. An automata-theoretic characterization of the OI-hierarchy. In ICALP 1982, 1982. Google Scholar
  9. S. A. Greibach. Remarks on blind and partially blind one-way multicounter machines. Theoretical Computer Science, 7(3):311-324, 1978. Google Scholar
  10. H. Gruber, M. Holzer, and M. Kutrib. The size of Higman-Haines sets. Theoretical Computer Science, 387(2):167-176, 2007. Google Scholar
  11. H. Gruber, M. Holzer, and M. Kutrib. More on the size of higman-haines sets: effective constructions. Fundamenta Informaticae, 91(1):105-121, 2009. Google Scholar
  12. E. M. Gurari and O. H. Ibarra. The complexity of decision problems for finite-turn multicounter machines. Journal of Computer and System Sciences, 22(2):220-229, 1981. Google Scholar
  13. C. Haase and P. Hofman. Tightening the complexity of equivalence problems for commutative grammars. In STACS 2016, 2016. Google Scholar
  14. P. Habermehl, R. Meyer, and H. Wimmel. The downward-closure of Petri net languages. In ICALP 2010, 2010. Google Scholar
  15. M. Hague, J. Kochems, and C.-H. L. Ong. Unboundedness and downward closures of higher-order pushdown automata. In POPL 2016, 2016. Google Scholar
  16. M. Hague and A. W. Lin. Model checking recursive programs with numeric data types. In CAV 2011, 2011. Google Scholar
  17. L. H. Haines. On free monoids partially ordered by embedding. Journal of Combinatorial Theory, 6(1):94-98, 1969. Google Scholar
  18. D. T. Huynh. The complexity of equivalence problems for commutative grammars. Information and Control, 66(1):103-121, 1985. Google Scholar
  19. O. H. Ibarra. Reversal-bounded multicounter machines and their decision problems. Journal of the ACM (JACM), 25(1):116-133, 1978. Google Scholar
  20. M. Jantzen and A. Kurganskyy. Refining the hierarchy of blind multicounter languages and twist-closed trios. Information and Computation, 185(2):159-181, 2003. Google Scholar
  21. P. Jullien. Contribution à létude des types d'ordres dispersés. PhD thesis, Université de Marseille, 1969. Google Scholar
  22. P. Karandikar, M. Niewerth, and Ph. Schnoebelen. On the state complexity of closures and interiors of regular languages with subwords and superwords. Theoretical Computer Science, 610, Part A:91-107, 2016. Google Scholar
  23. E. Kopczyński. Complexity of problems of commutative grammars. Logical Methods in Computer Science, 11(1), 2015. Google Scholar
  24. E. Kopczyński and A. W. To. Parikh images of grammars: Complexity and applications. In LICS 2010, 2010. Google Scholar
  25. M. Lohrey. Algorithmics on SLP-compressed strings: a survey. Groups Complexity Cryptology, 4(2):241-299, 2012. Google Scholar
  26. E. W. Mayr and A. R. Meyer. The complexity of the finite containment problem for petri nets. Journal of the ACM, 28(3):561-576, 1981. Google Scholar
  27. A. Okhotin. On the state complexity of scattered substrings and superstrings. Fundamenta Informaticae, 99(3):325-338, 2010. Google Scholar
  28. R. J. Parikh. On context-free languages. Journal of the ACM, 13(4):570-581, 1966. Google Scholar
  29. L. Pottier. Minimal solutions of linear diophantine systems : bounds and algorithms. In RTA 1991, 1991. Google Scholar
  30. L. Priese and H. Wimmel. Petri-Netze. Springer-Verlag, 2003. Google Scholar
  31. N. Rampersad, J. Shallit, and Z. Xu. The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages. Fundamenta Informaticae, 116(1-4):223-236, 2012. Google Scholar
  32. S. La Torre, A. Muscholl, and I. Walukiewicz. Safety of Parametrized Asynchronous Shared-Memory Systems is Almost Always Decidable. In CONCUR 2015, 2015. Google Scholar
  33. J. van Leeuwen. Effective constructions in well-partially-ordered free monoids. Discrete Mathematics, 21(3):237-252, 1978. Google Scholar
  34. G. Zetzsche. An approach to computing downward closures. In ICALP 2015, 2015. Google Scholar
  35. G. Zetzsche. Computing downward closures for stacked counter automata. In STACS 2015, 2015. Google Scholar
  36. G. Zetzsche. The complexity of downward closure comparisons, 2016. URL: http://arxiv.org/abs/1605.03149.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact