52 citations · 113 across the 8 of their papers we have counts for
6 papers · 1 filter
Equivalence of Linear Tree Transducers with Output in the Free Group
Raphaela Löbel, Michael Luttenberger, Helmut Seidl
We show that equivalence of deterministic linear tree transducers can be decided in polynomial time when their outputs are interpreted over the free group. Due to the cancellation…
On the Balancedness of Tree-to-word Transducers
Raphaela Löbel, Michael Luttenberger, Helmut Seidl
A language over an alphabet of opening () and closing () brackets, is balanced if it is a subset of the Dyck language over , and…
Computing the longest common prefix of a context-free language in polynomial time
Michael Luttenberger, Raphaela Palenta, Helmut Seidl
We present two structural results concerning longest common prefixes of non-empty languages. First, we show that the longest common prefix of the language generated by a context-fr…
Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity
Georg Bachmeier, Michael Luttenberger, Maximilian Schlund
We answer two open questions by (Gruber, Holzer, Kutrib, 2009) on the state-complexity of representing sub- or superword closures of context-free grammars (CFGs): (1) We prove a (t…
An Extension of Parikh's Theorem beyond Idempotence
Michael Luttenberger, Maximilian Schlund
The commutative ambiguity of a context-free grammar G assigns to each Parikh vector v the number of distinct leftmost derivations yielding a word with Parikh vector v. Based on the…
Parikh's Theorem: A simple and direct automaton construction
Javier Esparza, Pierre Ganty, Stefan Kiefer +1
Parikh's theorem states that the Parikh image of a context-free language is semilinear or, equivalently, that every context-free language has the same Parikh image as some regular…