Linear time and the power of one first-order universal quantifier

DOI10.1016/S0890-5401(02)93027-0zbMath1012.68084OpenAlexW2041797146MaRDI QIDQ1854556

Arnaud Durand

Publication date: 14 January 2003

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

Full work available at URL: https://doi.org/10.1016/s0890-5401(02)93027-0

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19)

Cites Work

• Unnamed Item
• Unnamed Item
• First-order spectra with one variable
• The quantifier structure of sentences that characterize nondeterministic time complexity
• Monadic logical definability of nondeterministic linear time
• Invariance properties of RAMs and linear time
• First-order spectra with one binary predicate
• The monadic second-order logic of graphs. X: Linear orderings
• Sorting, linear time and the satisfiability problem
• A Nontrivial Lower Bound for an NP Problem on Automata
• Relational queries computable in polynomial time
• Complexity classes and theories of finite models
• Linear Time Algorithms and NP-Complete Problems
• Subclasses of binary NP
• On bijections vs. unary functions

This page was built for publication: Linear time and the power of one first-order universal quantifier