On the equivalence of some transductions involving letter to letter morphisms on regular languages

DOI10.1007/BF00288471zbMath0564.68056OpenAlexW2033226842MaRDI QIDQ1058303

Yael Maon

Publication date: 1986

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00288471

zbMATH Keywords

decidabilityregular languagesEquivalence problemsfinite substitutions

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Word problems, etc. in computability and recursion theory (03D40)

Related Items (8)

A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\) ⋮ Balance of many-valued transductions and equivalence problems ⋮ Identities and transductions ⋮ On some transducer equivalence problems for families of languages ⋮ Unnamed Item ⋮ The undecidability of some equivalence problems concerning ngsm's and finite substitutions ⋮ On the equivalence of some transductions involving letter to letter morphisms on regular languages ⋮ On the equivalence problem of compositions of morphisms and inverse morphisms on context-free languages

Cites Work

• On some decision questions concerning pushdown machines
• 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
• Inverse morphic equivalence on languages
• On the equivalence problem of compositions of morphisms and inverse morphisms on context-free languages
• Balance of many-valued transductions and equivalence problems
• Single-valued a-transducers
• On the decidability of homomorphism equivalence for languages
• Some decidability results about regular and pushdown translations
• A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language
• Test sets for context free languages and algebraic systems of equations over a free monoid
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the equivalence of some transductions involving letter to letter morphisms on regular languages