Homomorphism equivalence on etol languages†

†This research was supported by the National Research Council of Canada Grant No. A7403.

Abstract

The following problems are shown to be decidable. Given an ETOL language L and two homomorphisms h ₁ h ₂is the length (Parikh vector) of h ₁(x) and h ₂(x) equal for each x in L? If Lis over a binary alphabet then we can also test whether h ₁(x)= h ₂(x) for each x in L.

Keywords:

• Decidability
• L-systems
• homomorphic euqivalence
• Pakirh mappings

C.R. Categories:

• 5.23
• 5.27

†This research was supported by the National Research Council of Canada Grant No. A7403.

‡This paper was written during the second author's stay at the University of Waterloo. Waterloo, Ontario, Canada.

†This research was supported by the National Research Council of Canada Grant No. A7403.

‡This paper was written during the second author's stay at the University of Waterloo. Waterloo, Ontario, Canada.

Notes

†This research was supported by the National Research Council of Canada Grant No. A7403.

‡This paper was written during the second author's stay at the University of Waterloo. Waterloo, Ontario, Canada.