Some Decision Questions Concerning the Time Complexity of Language Acceptors

DOI10.1007/978-3-642-38771-5_24MaRDI QIDQ5300846zbMATH OpenOpenAlexFDO

Authors Oscar H. Ibarra, B. Ravikumar

Publication date 28 June 2013

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-38771-5_24

zbMATH Keywords

\(k\)-ambiguouscounter machinedecidableGSMNFANPDAreversal-bounded countersrun-time equivalencetime complexityunambiguousundecidable

Mathematics Subject Classification ID

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

Recommendations

• SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS
• Complexity of certain decision problems about congruential languages
• On languages accepted with simultaneous complexity bounds and their ranking problem
• Languages, Decidability, and Complexity
• On the acceptance power of regular languages
• scientific article; zbMATH DE number 3870629
• On the complexity of decidable cases of the commutation problem of languages
• On the complexity of a mildly context-sensitive language class
• scientific article; zbMATH DE number 4035114
• scientific article; zbMATH DE number 3978429

Cited in

(2)

• On store languages of language acceptors
• SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS

This page was built for publication: Some Decision Questions Concerning the Time Complexity of Language Acceptors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300846)