Test sets and checking words for homomorphism equivalence

DOI10.1016/0022-0000(80)90013-6zbMath0451.68046OpenAlexW2055420198MaRDI QIDQ1148122

Karel II Culik, Arto Salomaa

Publication date: 1980

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(80)90013-6

zbMATH Keywords

Ehrenfeucht's conjecturehomomorphism equivalence

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (20)

A proof of Ehrenfeucht's conjecture ⋮ PCP-prime words and primality types ⋮ The descending chain condition on solution sets for systems of equations in groups ⋮ 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 ⋮ Strongly prime PCP words ⋮ Unnamed Item ⋮ Polynomial size test sets for context-free languages ⋮ A closure property of deterministic context-free languages ⋮ New techniques for proving the decidability of equivalence problem ⋮ 2DST mappings of languages and related problems ⋮ Efficient constructions of test sets for regular and context-free languages ⋮ Checking sets, test sets, rich languages and commutatively closed languages ⋮ Systems of equations over a free monoid and Ehrenfeucht's conjecture ⋮ On binary equality sets and a solution to the test set conjecture in the binary case ⋮ The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids ⋮ On test sets for checking morphism equivalence on languages with fair distribution of letters ⋮ On cancellation properties of languages which are supports of rational power series ⋮ Test sets for morphisms with bounded delay

Cites Work

• On the decidability of homomorphism equivalence for languages
• Elementary homomorphisms and a solution of the DOL sequence equivalence problem
• The decidability of the equivalence problem for DOL-systems
• A Purely Homomorphic Characterization of Recursively Enumerable Sets
• Homomorphism equivalence on etol languages†
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Test sets and checking words for homomorphism equivalence