A note on finite-valued and finitely ambiguous transducers

DOI10.1007/BF01744569zbMath0502.68022OpenAlexW2011523226MaRDI QIDQ3968472

Oscar H. Ibarra, Eitan M. Gurari

Publication date: 1983

Published in: Mathematical Systems Theory (Search for Journal in Brave)

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

zbMATH Keywords

equivalencedecision problemspolynomial time algorithmfinite ambiguityfinite- valuednessnondeterministic finite transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (34)

Lossiness of communication channels modeled by transducers1 ⋮ Finite-valued distance automata ⋮ The equivalence of finite valued transducers (on HDT0L languages) is decidable ⋮ Multi-sequential Word Relations ⋮ FORMAL DESCRIPTIONS OF CODE PROPERTIES: DECIDABILITY, COMPLEXITY, IMPLEMENTATION ⋮ Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ Deterministic realization of nondeterministic computations with a low measure of nondeterminism ⋮ Deciding the immutability of regular codes and languages under finite transduction ⋮ Visibly pushdown transducers ⋮ Prefix and equality languages of rational functions are co-context-free ⋮ On the decidability of the valuedness problem for two-way finite transducers ⋮ Equivalence Checking Problem for Finite State Transducers over Semigroups ⋮ On the containment and equivalence problems for two-way transducers ⋮ Lexicographic decomposition of \(k\)-valued transducers ⋮ On the Decidability of the Equivalence for k-Valued Transducers ⋮ Static analysis of XML security views and query rewriting ⋮ On the finite-valuedness problem for sequential machines ⋮ The Equivalence Problem of Finite Substitutions on ab*c, with Applications ⋮ FINITELY SUBSEQUENTIAL TRANSDUCERS ⋮ There does not exist an enumerable family of context-free grammars that generates the class of single-valued languages ⋮ Multi-Sequential Word Relations ⋮ Nondeterministic Streaming String Transducers ⋮ Efficient constructions of test sets for regular and context-free languages ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Containment and Equivalence Problems for GSMs, Transducers, and Linear CFGs ⋮ Transducing reversibly with finite state machines ⋮ Transforming a single-valued transducer into a Mealy machine ⋮ Finite transducers and rational transductions ⋮ SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS ⋮ Decomposing a $k$-valued transducer into $k$ unambiguous ones ⋮ A Pattern Logic for Automata with Outputs ⋮ Squaring transducers: An efficient procedure for deciding functionality and sequentiality. ⋮ On the lengths of values in a finite transducer

Cites Work

• Unnamed Item
• Unnamed Item
• The decidability of equivalence for deterministic finite transducers
• The complexity of decision problems for finite-turn multicounter machines
• On the finite-valuedness problem for sequential machines
• Single-valued a-transducers
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• A Polynomial Time Algorithm for Deciding the Equivalence Problem for 2-Tape Deterministic Finite State Acceptors
• 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

This page was built for publication: A note on finite-valued and finitely ambiguous transducers