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

DOI10.1016/S0020-0190(96)00198-6MaRDI QIDQ286970zbMATH OpenFDO

Authors Bernd Loescher

Publication date 26 May 2016

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

zbMATH Keywords

computational complexityfinite model theoryexistential second-order logicformal languages

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1223621
• First-order spectra with one binary predicate
• First-order spectra with one variable
• scientific article; zbMATH DE number 2079026
• Spectra and satisfiability for logics with successor and a unary function

Cites work

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

Cited in

(3)

• Fifty years of the spectrum problem: survey and new results
• 2002 European Summer Meeting of the Association for Symbolic Logic Logic Colloquium '02
• On bijections vs. unary functions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q286970)