Document Open Access Logo

Computing Downward Closures for Stacked Counter Automata

Author Georg Zetzsche

PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.743.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Georg Zetzsche

Cite As Get BibTex

Georg Zetzsche. Computing Downward Closures for Stacked Counter Automata. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 743-756, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.STACS.2015.743

Abstract

The downward closure of a language L of words is the set of all (not necessarily contiguous) subwords of members of L. It is well known that the downward closure of any language is regular. Although the downward closure seems to be a promising abstraction, there are only few language classes for which an automaton for the downward closure is known to be computable.  It is shown here that for stacked counter automata, the downward closure is computable.  Stacked counter automata are finite automata with a storage mechanism obtained by adding blind counters and building stacks. Hence, they generalize pushdown and blind counter automata.  The class of languages accepted by these automata are precisely those in the hierarchy obtained from the context-free languages by alternating two closure operators: imposing semilinear constraints and taking the algebraic extension. The main tool for computing downward closures is the new concept of Parikh annotations.  As a second application of Parikh annotations, it is shown that the hierarchy above is strict at every level.

Subject Classification

Keywords
  • abstraction
  • downward closure
  • obstruction set
  • computability

Metrics

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

References

  1. Parosh Aziz Abdulla, Luc Boasson, and Ahmed Bouajjani. Effective lossy queue languages. In Proc. of ICALP 2001, volume 2076 of LNCS, pages 639-651. Springer, 2001. Google Scholar
  2. Mohamed Faouzi Atig, Ahmed Bouajjani, and Shaz Qadeer. Context-bounded analysis for concurrent programs with dynamic creation of threads. In Proc. of TACAS 2009, volume 5505 of LNCS, pages 107-123. Springer, 2009. Google Scholar
  3. Georg Bachmeier, Michael Luttenberger, and Maximilian Schlund. Finite automata for the sub- and superword closure of cfls: Descriptional and computational complexity, 2015. To appear in: Proceedings of LATA 2015. Google Scholar
  4. P. Buckheister and Georg Zetzsche. Semilinearity and context-freeness of languages accepted by valence automata. In Proc. of MFCS 2013, volume 8087 of LNCS, pages 231-242. Springer, 2013. Google Scholar
  5. Bruno Courcelle. On constructing obstruction sets of words. Bulletin of the EATCS, 44:178-186, 1991. Google Scholar
  6. Leonard Eugene Dickson. Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors. American Journal of Mathematics, 35(4):413-422, 1913. Google Scholar
  7. Hermann Gruber, Markus Holzer, and Martin Kutrib. The size of Higman-Haines sets. Theoretical Computer Science, 387(2):167-176, 2007. Google Scholar
  8. Hermann Gruber, Markus Holzer, and Martin Kutrib. More on the size of higman-haines sets: effective constructions. Fundamenta Informaticae, 91(1):105-121, 2009. Google Scholar
  9. Peter Habermehl, Roland Meyer, and Harro Wimmel. The downward-closure of Petri net languages. In Proc. of ICALP 2010, volume 6199 of LNCS, pages 466-477. Springer, 2010. Google Scholar
  10. Graham Higman. Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society. Third Series, 2:326-336, 1952. Google Scholar
  11. Prateek Karandikar and Philippe Schnoebelen. On the state complexity of closures and interiors of regular languages with subwords. In Proc. of DCFS 2014, volume 8614 of LNCS, pages 234-245. Springer, 2014. Google Scholar
  12. Eryk Kopczynski and Anthony Widjaja To. Parikh images of grammars: Complexity and applications. In Proc. of LICS 2010, pages 80-89. IEEE, 2010. Google Scholar
  13. Zhenyue Long, Georgel Calin, Rupak Majumdar, and Roland Meyer. Language-theoretic abstraction refinement. In Proc. of FASE 2012, volume 7212 of LNCS, pages 362-376. Springer, 2012. Google Scholar
  14. Richard Mayr. Undecidable problems in unreliable computations. Theoretical Computer Science, 297(1-3):337-354, 2003. Google Scholar
  15. Alexander Okhotin. On the state complexity of scattered substrings and superstrings. Fundamenta Informaticae, 99(3):325-338, 2010. Google Scholar
  16. Jan van Leeuwen. A generalisation of Parikh’s theorem in formal language theory. In Proc. of ICALP 1974, volume 14 of LNCS, pages 17-26. Springer, 1974. Google Scholar
  17. Jan van Leeuwen. Effective constructions in well-partially-ordered free monoids. Discrete Mathematics, 21(3):237-252, 1978. Google Scholar
  18. Georg Zetzsche. Computing downward closures for stacked counter automata. Google Scholar
  19. Georg Zetzsche. Silent transitions in automata with storage. In Proc. of ICALP 2013, volume 7966 of LNCS, pages 434-445. Springer, 2013. Google Scholar
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