On the decidability of homomorphism equivalence for languages

DOI10.1016/0022-0000(78)90002-8zbMath0389.68042OpenAlexW2071271929MaRDI QIDQ1251076

Arto Salomaa, Karel II Culik

Publication date: 1978

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(78)90002-8

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (33)

Some decision problems concerning semilinearity and commutation. ⋮ Systèmes entiers d'équations sur un alphabet fini et conjecture d'Ehrenfeucht ⋮ The equivalence of finite valued transducers (on HDT0L languages) is decidable ⋮ Balance of many-valued transductions and equivalence problems ⋮ Equivalence problem of mappings relative to languages ⋮ Unnamed Item ⋮ Every finitely generated submonoid of a free monoid has a finite Malcev's presentation ⋮ On the equivalence problem for deterministic multitape automata and transducers ⋮ Polynomial size test sets for context-free languages ⋮ Test sets and checking words for homomorphism equivalence ⋮ New techniques for proving the decidability of equivalence problem ⋮ 2DST mappings of languages and related problems ⋮ On some transducer equivalence problems for families of languages ⋮ Multiplicities: A deterministic view of nondeterminism ⋮ Efficient constructions of test sets for regular and context-free languages ⋮ Equations over finite sets of words and equivalence problems in automata theory ⋮ A note on undercover relation ⋮ HDTOL matching of computations of multitape automata ⋮ Some decidability results about regular and pushdown translations ⋮ A homomorphic characterization of time and space complexity classes of languages† ⋮ Unnamed Item ⋮ A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language ⋮ Synchronizable deterministic pushdown automata and the decidability of their equivalence ⋮ Finite transducers and rational transductions ⋮ Checking sets, test sets, rich languages and commutatively closed languages ⋮ Dominoes over a free monoid ⋮ Systems of equations over a free monoid and Ehrenfeucht's conjecture ⋮ On the equivalence of some transductions involving letter to letter morphisms on regular languages ⋮ The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids ⋮ Inverse morphic equivalence on languages ⋮ On test sets for checking morphism equivalence on languages with fair distribution of letters ⋮ Test sets for morphisms with bounded delay ⋮ On the equivalence problem of compositions of morphisms and inverse morphisms on context-free languages

Cites Work

• Unnamed Item
• On the decidability of the sequence equivalence problem for DOL-systems
• On sentential forms of context-free grammars
• The decidability of the equivalence problem for DOL-systems
• On the decidability of some equivalence problems for DOL-systems

This page was built for publication: On the decidability of homomorphism equivalence for languages