Relativized logspace and generalized quantifiers over finite ordered structures

DOI10.2307/2275546zbMath0882.03031OpenAlexW2007155273MaRDI QIDQ4358054

Georg Gottlob

Publication date: 28 September 1997

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2275546

zbMATH Keywords

expressive powerrelativizationoracleordered structureslogspaceHenkin quantifierscomplexity classbounded queriesfirst-order logic with generalized quantifiers over finite

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (9)

A finite model-theoretical proof of a property of bounded query classes within PH ⋮ A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison ⋮ Logics capturing relativized complexity classes uniformly ⋮ Computing LOGCFL certificates ⋮ 2002 European Summer Meeting of the Association for Symbolic Logic Logic Colloquium '02 ⋮ Partially ordered connectives and monadic monotone strict NP ⋮ Succinctness as a source of complexity in logical formalisms ⋮ On the complexity of data disjunctions. ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws

Cites Work

• Unnamed Item
• Henkin quantifiers and complete problems
• The method of forced enumeration for nondeterministic automata
• Relativized alternation and space-bounded computation
• Using the Hamiltonian path operator to capture NP
• A comparison of polynomial time reducibilities
• Log space machines with multiple oracle tapes
• Mechanizing hypothesis formation. Mathematical foundations for a general theory
• Definability hierarchies of generalized quantifiers
• Generalized quantifiers and pebble games on finite structures
• On the Decomposability of $NC$ and $AC$
• Comparing the Expressibility of Languages Formed Using NP-Complete Operators
• Bounded Query Classes
• RelativizedNC
• Languages that Capture Complexity Classes
• Nondeterministic Space is Closed under Complementation
• Complete Problems Involving Boolean Labelled Structures and Projection Transactions
• Relativization of questions about log space computability
• Generalized theorems on relationships among reducibility notions to certain complexity classes
• Generalized Quantifiers and Logical Reducibilities
• On computing Boolean connectives of characteristic functions

This page was built for publication: Relativized logspace and generalized quantifiers over finite ordered structures