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

DOI10.1016/S0304-3975(96)00246-0MaRDI QIDQ1269922zbMATH OpenFDO

Authors Paavo Turakainen

Publication date 22 October 1998

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

Full work available at URL https://doi.org/10.1016/S0304-3975(96)00246-0

zbMATH Keywords

linear grammars

Mathematics Subject Classification ID

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

Recommendations

• Undecidability of the equivalence of finite substitutions on regular language
• The equivalence problem for finite substitutions in a regular language
• The \(n\)-r.e. degrees: undecidability and \(\Sigma_1\) substructures
• A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\)
• scientific article; zbMATH DE number 1688379
• Publication:4952569
• A note on the decidability of subword inequalities
• Publication:4941151
• UNDECIDABILITY, AUTOMATA, AND PSEUDOVARITIES OF FINITE SEMIGROUPS
• Decidable subcases of the equivalence problem for recursive program schemes

Cites work

• Cardinality problems of compositions of morphisms and inverse morphisms
• Equations over finite sets of words and equivalence problems in automata theory
• scientific article; zbMATH DE number 3970124 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• scientific article; zbMATH DE number 572102 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• On some transducer equivalence problems for families of languages
• On the equivalence of some transductions involving letter to letter morphisms on regular languages
• 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

Cited in

(7)

• A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\)
• Finite transducers and rational transductions
• Undecidability of the word problem for Yamamura's HNN-extension under nice conditions.
• Undecidability of the equivalence of finite substitutions on regular language
• scientific article; zbMATH DE number 1091113 (Why is no real title available?)
• On the containment and equivalence problems for GSMs, transducers, and linear CFGs
• The Equivalence Problem of Finite Substitutions on ab*c, with Applications

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1269922)