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

DOI10.1016/S0020-0190(96)00198-6zbMATH Open1336.68110MaRDI QIDQ286970FDOQ286970

Authors: Bernd Loescher 

Publication date: 26 May 2016

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

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

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)

Cites Work

• On monadic NP vs monadic co-NP
• On winning Ehrenfeucht games and monadic NP
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Monadic generalized spectra
• Title not available (Why is that?)
• A note on the number of monadic quantifiers in monadic \(\Sigma ^{1}_{1}\)
• First-order spectra with one variable

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)