Name
Abstract | ||
|---|---|---|
One-dimensional fragment of first-order logic is obtained by restricting quantification to blocks of existential quantifiers that leave at most one variable free. We investigate one-dimensional fragment over words and over omega-words. We show that it is expressively equivalent to the two-variable fragment of first-order logic. We also show that its satisfiability problem is NExpTime-complete. Further, we show undecidability of some extensions, whose two-variable counterparts remain decidable. |
Year | Venue | Field |
|---|---|---|
2016 | CSL | Discrete mathematics,Computer science,Boolean satisfiability problem,Zeroth-order logic,Description logic,Decidability,Linear temporal logic,Predicate logic,Higher-order logic |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Emanuel Kieronski | 1 | 114 | 13.85 |