Nonerasing, counting, and majority over the linear time hierarchy

DOI10.1006/inco.2001.3084zbMath1009.68051OpenAlexW2012707656MaRDI QIDQ1854524

Arnaud Durand, Malika More

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2001.3084

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Extensions of MSO and the monadic counting hierarchy ⋮ Observations on complete sets between linear time and polynomial time ⋮ On the expressive power of monadic least fixed point logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On quasilinear-time complexity theory
• The complexity of combinatorial problems with succinct input representation
• Relativized alternation and space-bounded computation
• Rudimentary relations and primitive recursion: A toolbox
• A machine description and the hierarchy of initial Grzegorczyk classes
• On counting problems and the polynomial-time hierarchy
• The polynomial-time hierarchy
• Monadic logical definability of nondeterministic linear time
• Sharply bounded alternation and quasilinear time
• Nondeterministic stack register machines
• Sorting, linear time and the satisfiability problem
• Counting $Δ_0$ sets
• Theory of Formal Systems. (AM-47)
• ON THE NOTION OF LINEAR TIME COMPUTABILITY
• The Complexity of Enumeration and Reliability Problems
• Small Grzegorczyk classes and limited minimum
• Satisfiability Is Quasilinear Complete in NQL
• Rudimentary Predicates and Relative Computation
• Linear Time Algorithms and NP-Complete Problems
• Complexity classes defined by counting quantifiers
• Rudimentary Languages and Second‐Order Logic
• Context-free languages and rudimentary attributes