Monadic logical definability of nondeterministic linear time

DOI10.1007/PL00001594zbMath0913.03040OpenAlexW2029100403MaRDI QIDQ1266167

Frédéric Olive, Etienne Grandjean

Publication date: 24 May 1999

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/pl00001594

zbMATH Keywords

computational complexitymonadic second-order logicnondeterminismlinear timefinite model theoryNP-complete problemdescriptive complexity theoryrandom access machineunary functions

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Interpolation, preservation, definability (03C40)

Related Items (4)

Graph properties checkable in linear time in the number of vertices ⋮ Nonerasing, counting, and majority over the linear time hierarchy ⋮ Linear time and the power of one first-order universal quantifier ⋮ On the expressive power of monadic least fixed point logic

This page was built for publication: Monadic logical definability of nondeterministic linear time