One unary function says less than two in existential second order logic

DOI10.1016/S0020-0190(96)00198-6zbMath1336.68110MaRDI QIDQ286970

Bernd Loescher

Publication date: 26 May 2016

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

zbMATH Keywords

computational complexityformal languagesfinite model theoryexistential second-order logic

Mathematics Subject Classification ID

Logic in computer science (03B70) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items (2)

Fifty years of the spectrum problem: survey and new results ⋮ 2002 European Summer Meeting of the Association for Symbolic Logic Logic Colloquium '02

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the number of monadic quantifiers in monadic \(\Sigma ^{1}_{1}\)
• First-order spectra with one variable
• On monadic NP vs monadic co-NP
• On winning Ehrenfeucht games and monadic NP
• An application of games to the completeness problem for formalized theories
• Reachability is harder for directed than for undirected finite graphs
• Universal quantifiers and time complexity of random access machines
• A Natural NP-Complete Problem with a Nontrivial Lower Bound
• Second-order and Inductive Definability on Finite Structures
• Monadic generalized spectra

This page was built for publication: One unary function says less than two in existential second order logic