Loading...
Please wait, while we are loading the content...
Similar Documents
Decidability issues for two-variable logics with several linear orders (2011).
| Content Provider | CiteSeerX |
|---|---|
| Author | KieroĊski, Emanuel |
| Abstract | We show that the satisfiability and the finite satisfiability problems for two-variable logic, FO 2, over the class of structures with three linear orders, are undecidable. This sharpens an earlier result that FO 2 with eight linear orders is undecidable. The theorem holds for a restricted case in which linear orders are the only non-unary relations. Recently, a contrasting result has been shown, that the finite satisfiability problem for FO 2 with two linear orders and with no additional non-unary relations is decidable. We observe that our proof can be adapted to some interesting fragments of FO 2, in particular it works for the two-variable guarded fragment, GF 2, even if the order relations are used only as guards. Finally, we show that GF 2 with an arbitrary number of linear orders which can be used only as guards becomes decidable if except linear orders only unary relations are allowed. |
| File Format | |
| Publisher Date | 2011-01-01 |
| Access Restriction | Open |
| Subject Keyword | Linear Order Two-variable Logic Decidability Issue Several Linear Order Finite Satisfiability Problem Two-variable Guarded Fragment Non-unary Relation Arbitrary Number Order Relation Unary Relation Interesting Fragment Contrasting Result Additional Non-unary Relation Restricted Case |
| Content Type | Text |
