A fast algorithm to decide on simple grammars equivalence. (English) Zbl 0704.68072

Optimal algorithms, Proc. Int. Symp., Varna/Bulgaria 1989, Lect. Notes Comput. Sci. 401, 66-85 (1989).
[For the entire collection see Zbl 0704.68003.]
A branching algorithm is presented for a problem of simple grammars equivalence. Its time and space complexity is polynomial in the length of description and the valuations of compared grammars and exponential in the length of description only.
Reviewer: I.Martinec


68Q42 Grammars and rewriting systems
68Q25 Analysis of algorithms and problem complexity


Zbl 0704.68003