Décidabilité de l’égalité des langages algébriques infinitaires simples. (French) Zbl 0595.68072

Theoretical aspects of computer science, 3rd Annu. Symp., Orsay/France 1986, Lect. Notes Comput. Sci. 210, 37-48 (1986).
[For the entire collection see Zbl 0578.00004.]
An infinitary simple language (ISL) is a language generated by a simple grammar, to which the set of infinite terminal words is added such that any left factor is a left factor of a derivation. The ISL equality and the equivalence of monadic recursive program schemes (as defined by Nivat) are two inter-reducible problems. For any simple grammar G, we define the infinitary equivalence \(\equiv_ G\) as being the set of nonterminal word pairs generating the same ISL, and we show that \(\equiv_ G\) is finitely generated. From that property, we deduce a decision algorithm for \(\equiv_ G\) with complexity polynomial in time and space in the evaluation and the description length of the grammar, and exponential when regarding the latter parameter only (if we reduce the ISL equality problem to that of the equivalence of the stateless dpda with acceptance on pushdown letters - the equivalence algorithm of Oyamaguchi and Honda -, we obtain a double exponential algorithm). Thanks to this work, we have obtained new results concerning the equivalence problem for context-free grammars.


68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity


Zbl 0578.00004