On some transducer equivalence problems for families of languages
From MaRDI portal
Publication:3806848
DOI10.1080/00207168808803611zbMath0658.68097OpenAlexW1974626062WikidataQ126245788 ScholiaQ126245788MaRDI QIDQ3806848
Publication date: 1988
Published in: International Journal of Computer Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/00207168808803611
undecidabilityregular languagestest setsequality languagerational formal power seriesrational languagefunctional equivalencedeterministic generalized sequential machinesfunctional transducerstrongly uniform morphism
Related Items (8)
A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\) ⋮ Equivalence problem of mappings relative to languages ⋮ The equivalence of deterministic gsm replications onQ-rational languages is decidable ⋮ The Equivalence Problem of Finite Substitutions on ab*c, with Applications ⋮ The undecidability of some equivalence problems concerning ngsm's and finite substitutions ⋮ Equivalence of transducers relative to regular languages ⋮ Solvability problems for \(ND\)-systems ⋮ On the power of synchronization in parallel computations
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The decidability of equivalence for deterministic finite transducers
- On the equivalence of some transductions involving letter to letter morphisms on regular languages
- Inverse morphic equivalence on languages
- On cancellation properties of languages which are supports of rational power series
- On the equivalence problem of compositions of morphisms and inverse morphisms on context-free languages
- Cônes rationnels commutatifs
- Multiple equality sets and Post machines
- 2DST mappings of languages and related problems
- One counter languages and the IRS condition
- Produit dans le cône rationnel engendre par D
- 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
- On some bounded semiAFLs and AFLs
- Test sets for context free languages and algebraic systems of equations over a free monoid
- Two-way counter machines and finite-state transducers†
- Equality languages and fixed point languages
- Test sets for homomorphism equivalence on context free languages
- Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
- The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable
- The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
- A note on undecidable properties of formal languages
- The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
This page was built for publication: On some transducer equivalence problems for families of languages
