SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS

DOI10.1142/S0129054114400280zbMath1310.68132MaRDI QIDQ5247179

Oscar H. Ibarra, Bala Ravikumar

Publication date: 23 April 2015

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

zbMATH Keywords

GSMtime complexityreversal-bounded counterscounter machinedecidableNFAPDAundecidableunambiguousNFT\(k\)-ambiguousrun-time equivalence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Undecidability and degrees of sets of sentences (03D35)

Related Items

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

Cites Work

• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• The equivalence problem of multitape finite automata
• Limitedness theorem on finite automata with distance functions
• On the valuedness of finite transducers
• The complexity of decision problems for finite-turn multicounter machines
• On the finite-valuedness problem for sequential machines
• Reversal-bounded multipushdown machines
• The limitedness problem on distance automata: Hashiguchi's method revisited
• A note on finite-valued and finitely ambiguous transducers
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
• New Decidability Results Concerning Two-Way Counter Machines
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• One-way stack automata