Linear time and the power of one first-order universal quantifier
type: Item
instance of: scholarly article
title: Linear time and the power of one first-order universal quantifier
zbMATH Open document ID: 1012.68084
DOI: 10.1016/S0890-5401(02)93027-0
author: Arnaud Durand
published in: Information and Computation
publication date: 2003-01-14T00:00:00Z
Mathematics Subject Classification ID: 68Q19
zbMATH DE Number: 1853282
MaRDI profile type: Publication
cites work: The monadic second-order logic of graphs. X: Linear orderings
cites work: Subclasses of binary NP
cites work: First-order spectra with one binary predicate
cites work: Q4198056
cites work: First-order spectra with one variable
cites work: A Nontrivial Lower Bound for an NP Problem on Automata
cites work: Invariance properties of RAMs and linear time
cites work: Linear Time Algorithms and NP-Complete Problems
cites work: Sorting, linear time and the satisfiability problem
cites work: Monadic logical definability of nondeterministic linear time
cites work: Relational queries computable in polynomial time
cites work: Complexity classes and theories of finite models
cites work: The quantifier structure of sentences that characterize nondeterministic time complexity
cites work: Q4218942
cites work: On bijections vs. unary functions
full work available at URL: s0890-5401(02)93027-0
OpenAlex ID: W2041797146
description: scientific article; zbMATH DE number 1853282