On a complexity hierarchy between L and NL

DOI10.1016/0020-0190(88)90057-9zbMath0662.68046OpenAlexW2018791466MaRDI QIDQ1114402

Dung T. Huynh, Sang Cho

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90057-9

zbMATH Keywords

complexity class of languagesone-way nondeterministic counter machineunary knapsack

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

On languages accepted with simultaneous complexity bounds and their ranking problem ⋮ On the computational complexity of problems related to distinguishability sets ⋮ A note on the space complexity of some decision problems for finite automata ⋮ Knapsack problems for NL ⋮ On partially blind multihead finite automata. ⋮ On the universe, disjointness, and containment problems for simple machines

Cites Work

• Relationships between nondeterministic and deterministic tape complexities
• A taxonomy of problems with fast parallel algorithms
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• Finite-Turn Pushdown Automata