On the Complexity of a Problem on Monadic String Rewriting Systems
Ferucio Laurenţiu Ţiplea, Erkki Mäkinen · Journal of automata, languages and combinatorics · 2002
Computing the set of descendants of a regular language $L$ with respect to a monadic string rewriting system has proved to be very useful in developing decision algorithms for various problems on finitely presented monoids and context-free grammars. Recently, Esparza et al. [7] proved $O(ps^3)$ time and $O(ps^2)$ space bounds for this problem, where $p$ is the number of rules in the monadic string rewriting system and $s$ is the number of states in the automaton accepting $L$. Using synchronized emtension systems [10, 11, 12] we provide a new insight into the problem and present an $O(pr)$ time and space solution, where $p$ is as above and $r$ is the number of rules in the grammar generating $L$.