On the Ambiguity and Finite-Valuedness Problems in Acceptors and Transducers

DOI10.1142/S0129054115400092zbMath1330.68161MaRDI QIDQ5744131

Oscar H. Ibarra

Publication date: 17 February 2016

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

undecidabilitydecidabilityambiguitytransducerslossinessfinite-valuednessacceptors

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• On the open problem of Ginsburg concerning semilinear sets and related problems
• On the containment and equivalence problems for two-way transducers
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• The equivalence problem of multitape finite automata
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• On the valuedness of finite transducers
• The complexity of decision problems for finite-turn multicounter machines
• Properties of syntax directed translations
• Syntax directed translations and the pushdown assembler
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS
• On Relations Defined by Generalized Finite Automata
• Syntax-Directed Transduction
• A remark on finite transducers