9 citations · 15 across the 4 of their papers we have counts for
7 papers
Permutations of context-free, ET0L and indexed languages
Tara Brough, Laura Ciobanu, Murray Elder +1
For a language , we consider its cyclic closure, and more generally the language , which consists of all words obtained by partitioning words from into factors a…
The complexity of downward closure comparisons
Georg Zetzsche
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.…
Complexity of regular abstractions of one-counter languages
Mohamed Faouzi Atig, Dmitry Chistikov, Piotr Hofman +3
We study the computational and descriptional complexity of the following transformation: Given a one-counter automaton (OCA) A, construct a nondeterministic finite automaton (NFA)…
An approach to computing downward closures
Georg Zetzsche
The downward closure of a word language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of any language is regula…
Silent Transitions in Automata with Storage
Georg Zetzsche
We consider the computational power of silent transitions in one-way automata with storage. Specifically, we ask which storage mechanisms admit a transformation of a given automato…
Rational Subsets and Submonoids of Wreath Products
Markus Lohrey, Benjamin Steinberg, Georg Zetzsche
It is shown that membership in rational subsets of wreath products H \wr V with H a finite group and V a virtually free group is decidable. On the other hand, it is shown that ther…