License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.743
URN: urn:nbn:de:0030-drops-49554
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4955/
Go to the corresponding LIPIcs Volume Portal

Zetzsche, Georg

Computing Downward Closures for Stacked Counter Automata

pdf-format:
55.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{zetzsche:LIPIcs:2015:4955,
  author =	{Georg Zetzsche},
  title =	{{Computing Downward Closures for Stacked Counter Automata}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{743--756},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4955},
  URN =		{urn:nbn:de:0030-drops-49554},
  doi =		{10.4230/LIPIcs.STACS.2015.743},
  annote =	{Keywords: abstraction, downward closure, obstruction set, computability}
}

Keywords: abstraction, downward closure, obstruction set, computability
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI