9 citations · 25 across the 21 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.FL2016
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…
cs.FL2016
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.…
cs.FL2016
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)…