Hierarchies in transitive closure logic, stratified Datalog and infinitary logic (Q1919531): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0168-0072(95)00021-6 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2073314176 / rank | |||
Normal rank |
Revision as of 23:21, 19 March 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