Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
type: Item
instance of: scholarly article
title: Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
zbMATH Open document ID: 0856.03026
DOI: 10.1016/0168-0072(95)00021-6
author: Erich Grädel
author: Gregory Loren McColm
published in: Annals of Pure and Applied Logic
publication date: 1996-10-13T00:00:00Z
review text: By results due to Immerman we know that the fragment FO(posTC) of transitive closure logic FO(TC) which only allows positive applications of the TC operator has the same expressive power as FO(TC) on ordered finite structures. The main theorem of the present paper implies that FO(posTC) is not closed under negation -- and hence is different from FO(TC) -- on arbitrary finite structures. This result is obtained by embedding FO(posTC) and FO(TC) in \(L^\omega_{\infty \omega}\) and by showing a hierarchy theorem for prefix classes \(L^\omega_{\infty \omega}\). (This is achieved by using appropriate extensions of the Ehrenfeucht-Fraïssé games.) Among further applications, the authors derive a hierarchy theorem for transitive closure logic.
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 03C75
Mathematics Subject Classification ID: 68P15
zbMATH DE Number: 908460
zbMATH Keywords: infinitary logic
zbMATH Keywords: prefix classes
zbMATH Keywords: extensions of Ehrenfeucht-Fraïssé games
zbMATH Keywords: transitive closure logic
zbMATH Keywords: finite structures
zbMATH Keywords: hierarchy theorem
reviewed by: Jörg Flum
describes a project that uses: Datalog
describes a project that uses: GraphLog
MaRDI profile type: Publication
full work available at URL: 0168-0072(95)00021-6
OpenAlex ID: W2073314176
cites work: On Moschovakis closure ordinals
cites work: Henkin quantifiers and complete problems
cites work: Structure and complexity of relational queries
cites work: Horn clause queries and generalizations
cites work: Q3775538
cites work: An application of games to the completeness problem for formalized theories
cites work: Monadic generalized spectra
cites work: Q3230355
cites work: Q4202939
cites work: Fixed-point extensions of first-order logic
cites work: Number of quantifiers is better than number of tape cells
cites work: Upper and lower bounds for first order expressibility
cites work: Languages that Capture Complexity Classes
cites work: Relational queries computable in polynomial time
cites work: Nondeterministic Space is Closed under Complementation
cites work: Q3830533
cites work: Q4385543
cites work: The diversity of quantifier prefixes
cites work: The expressive power of stratified logic programs
cites work: Infinitary logics and 0-1 laws
cites work: Parametrization over inductive relations of a bounded number of variables
cites work: Elementary induction on abstract structures
cites work: The polynomial-time hierarchy
cites work: The method of forced enumeration for nondeterministic automata
cites work: Q3348436
cites work: Finite partially-ordered quantification
Recommended article: Q4230339
Recommended article: Hierarchies in independence and inclusion logic with strict semantics
Recommended article: FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
Recommended article: Fixpoint logics over hierarchical structures
Recommended article: Hierarchies in Dependence Logic
Recommended article: The defining power of stratified and hierarchical logic programs
Recommended article: Q5884936
Recommended article: Hierarchies in Inclusion Logic with Lax Semantics
Recommended article: On a hierarchy involving transitive closure logic and existential second-order quantification
description: scientific article; zbMATH DE number 908460