Hierarchies in transitive closure logic, stratified Datalog and infinitary logic (Q1919531): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Gregory Loren McColm / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Jörg Flum / rank | |||
Normal rank |
Revision as of 18:02, 15 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hierarchies in transitive closure logic, stratified Datalog and infinitary logic |
scientific article |
Statements
Hierarchies in transitive closure logic, stratified Datalog and infinitary logic (English)
0 references
13 October 1996
0 references
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.
0 references
infinitary logic
0 references
prefix classes
0 references
extensions of Ehrenfeucht-Fraïssé games
0 references
transitive closure logic
0 references
finite structures
0 references
hierarchy theorem
0 references