RAIRO - Theoretical Informatics and Applications · 2005 · 69 citations · 27 references
ComputingComputer ScienceMathematicsAlgorithmsDiscrete MathematicsTheory Of ComputationAutomata TheoryComputational ComplexityComputational ModelsFinite AutomataFinite-state MachinesStructural ComplexityComplexityFinite Automata TheoryStar Height
We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in 22O(n) space whether the language accepted by an n-state non-deterministic automaton is of a star height less than a given integer h (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity bound for the star height problem.
27
Transductions and Context-Free Languages
Jean Berstel · 1979 · 1.3K citations
Finite-state transducers in language and speech processing
Mehryar Mohri · 1997 · 922 citations