The undecidability of some equivalence problems concerning ngsm's and finite substitutions

DOI10.1016/S0304-3975(96)00246-0zbMath0908.68098MaRDI QIDQ1269922

Paavo Turakainen

Publication date: 22 October 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

linear grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (4)

A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\) ⋮ Undecidability of the equivalence of finite substitutions on regular language ⋮ The Equivalence Problem of Finite Substitutions on ab*c, with Applications ⋮ Finite transducers and rational transductions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equations over finite sets of words and equivalence problems in automata theory
• On the equivalence of some transductions involving letter to letter morphisms on regular languages
• On some transducer equivalence problems for families of languages
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
• Cardinality problems of compositions of morphisms and inverse morphisms
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines

This page was built for publication: The undecidability of some equivalence problems concerning ngsm's and finite substitutions