On the valuedness of finite transducers

DOI10.1007/BF00264285zbMath0672.68027MaRDI QIDQ1120286

S. H. Smith

Publication date: 1990

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

finite-valued nondeterministic generalized sequential machine Mvaluedness of finite transducers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (32)

Lossiness of communication channels modeled by transducers1 ⋮ Second-order finite automata: expressive power and simple proofs using automatic structures ⋮ Finite-valued distance automata ⋮ Multi-sequential Word Relations ⋮ Almost periodicity, finite automata mappings, and related effectiveness issues ⋮ Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ Automatic Kolmogorov complexity, normality, and finite-state dimension revisited ⋮ Equivalence of finite-valued tree transducers is decidable ⋮ On the decidability of the valuedness problem for two-way finite transducers ⋮ Equivalence Checking Problem for Finite State Transducers over Semigroups ⋮ Almost periodic sequences. ⋮ Observation and distinction: representing information in infinite games ⋮ Lexicographic decomposition of \(k\)-valued transducers ⋮ On the Decidability of the Equivalence for k-Valued Transducers ⋮ On the degree of ambiguity of finite automata ⋮ Finite-automaton transformations of strictly almost-periodic sequences ⋮ Multi-Sequential Word Relations ⋮ Nondeterministic Streaming String Transducers ⋮ Single-valuedness of tree transducers is decidable in polynomial time ⋮ On the Ambiguity and Finite-Valuedness Problems in Acceptors and Transducers ⋮ Using acceptors as transducers ⋮ On the Containment and Equivalence Problems for GSMs, Transducers, and Linear CFGs ⋮ Reasoning about strings in databases ⋮ Where Automatic Structures Benefit from Weighted Automata ⋮ Automatic Structures of Bounded Degree Revisited ⋮ Finite transducers and rational transductions ⋮ The isomorphism problem on classes of automatic structures with transitive relations ⋮ 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 ⋮ On the lengths of values in a finite transducer ⋮ Algorithmic aspects of decomposition and equivalence of finite-valued transducers

This page was built for publication: On the valuedness of finite transducers