The equivalence of finite valued transducers (on HDT0L languages) is decidable
From MaRDI portal
Publication:1090467
DOI10.1016/0304-3975(86)90134-9zbMath0621.68049OpenAlexW4212777194MaRDI QIDQ1090467
Karel II Culik, Juhani Karhumäki
Publication date: 1986
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(86)90134-9
test setequivalence problemgeneralization of the Ehrenfeucht ConjectureHDT0L languagenormalized k-valued finite transducers
Related Items
Decision problems of tree transducers with origin, Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines, Loops in automata and HDTOL relations, Equivalence of finite-valued tree transducers is decidable, On the equivalence problem for deterministic multitape automata and transducers, On the decidability of the valuedness problem for two-way finite transducers, Equivalence Checking Problem for Finite State Transducers over Semigroups, Systems of equations over a finite set of words and automata theory, On the containment and equivalence problems for two-way transducers, New techniques for proving the decidability of equivalence problem, Lexicographic decomposition of \(k\)-valued transducers, On the Decidability of the Equivalence for k-Valued Transducers, The Equivalence Problem of Finite Substitutions on ab*c, with Applications, There does not exist an enumerable family of context-free grammars that generates the class of single-valued languages, Nondeterministic Streaming String Transducers, Single-valuedness of tree transducers is decidable in polynomial time, Equations over finite sets of words and equivalence problems in automata theory, On the Ambiguity and Finite-Valuedness Problems in Acceptors and Transducers, Unnamed Item, Unnamed Item, HDTOL matching of computations of multitape automata, Unnamed Item, On the Containment and Equivalence Problems for GSMs, Transducers, and Linear CFGs, The equivalence problem for languages defined by transductions on D0L languages, Extended symbolic finite automata and transducers, Copyful Streaming String Transducers, Finite transducers and rational transductions, On D0L systems with immigration, On the lengths of values in a finite transducer, Algorithmic aspects of decomposition and equivalence of finite-valued transducers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The decidability of equivalence for deterministic finite transducers
- The equivalence problem for deterministic two-tape automata
- Systems of equations over a free monoid and Ehrenfeucht's conjecture
- The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
- On cancellation properties of languages which are supports of rational power series
- Test sets for finite substitutions
- A proof of Ehrenfeucht's conjecture
- Test sets and checking words for homomorphism equivalence
- 2DST mappings of languages and related problems
- Complete problems for deterministic polynomial time
- Single-valued a-transducers
- On the decidability of homomorphism equivalence for languages
- Some decidability results about regular and pushdown translations
- Explicit test sets for iterated morphisms in free monoids and metabelian groups
- Multitape one-way nonwriting automata
- Test sets for context free languages and algebraic systems of equations over a free monoid
- Two-way counter machines and finite-state transducers†
- The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable
- The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable
- A note on finite-valued and finitely ambiguous transducers
- The decidability of the equivalence problem for DOL-systems
- 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
