Homomorphism equivalence on etol languages†
- 1 January 1979
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 7 (1) , 43-51
- https://doi.org/10.1080/00207167908803155
Abstract
The following problems are shown to be decidable. Given an ETOL language L and two homomorphisms h 1 h 2is the length (Parikh vector) of h 1(x) and h 2(x) equal for each x in L? If Lis over a binary alphabet then we can also test whether h 1(x)= h 2(x) for each x in L.Keywords
This publication has 7 references indexed in Scilit:
- The ultimate equivalence problem for DOL systemsActa Informatica, 1978
- Automata-Theoretic Aspects of Formal Power SeriesPublished by Springer Nature ,1978
- The decidability of the equivalence problem for DOL-systemsInformation and Control, 1977
- On the decidability of the sequence equivalence problem for DOL-systemsTheoretical Computer Science, 1976
- Nonterminals versus homomorphisms in defining languages for some classes of rewriting systemsActa Informatica, 1974
- Programmed Grammars and Classes of Formal LanguagesJournal of the ACM, 1969
- Indexed Grammars—An Extension of Context-Free GrammarsJournal of the ACM, 1968