OpenBU

Fixed Point vs. First-Order Logic on Finite Ordered Structures with Unary Relations

OpenBU

Show simple item record

dc.contributor.author Kfoury, A.J.
dc.contributor.author Wymann-Böni, M.
dc.date.accessioned 2011-09-12T14:25:46Z
dc.date.available 2011-09-12T14:25:46Z
dc.date.issued 1993-08-11
dc.identifier.uri http://hdl.handle.net/2144/1471
dc.description.abstract We prove that first order logic is strictly weaker than fixed point logic over every infinite classes of finite ordered structures with unary relations: Over these classes there is always an inductive unary relation which cannot be defined by a first-order formula, even when every inductive sentence (i.e., closed formula) can be expressed in first-order over this particular class. Our proof first establishes a property valid for every unary relation definable by first-order logic over these classes which is peculiar to classes of ordered structures with unary relations. In a second step we show that this property itself can be expressed in fixed point logic and can be used to construct a non-elementary unary relation. en_US
dc.description.sponsorship NSF (CCR-9113196), Swiss National Science Foundation en_US
dc.language.iso en_US en_US
dc.publisher Boston University Computer Science Department en_US
dc.relation.ispartofseries BUCS Technical Reports;BUCS-TR-1993-008
dc.title Fixed Point vs. First-Order Logic on Finite Ordered Structures with Unary Relations en_US
dc.type Technical Report en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search OpenBU


Browse

Deposit Materials

Statistics