Name
Abstract | ||
|---|---|---|
One-dimensional fragment of first-order logic is obtained by restricting quantification to blocks of existential (universal) quantifiers that leave at most one variable free. We investigate this fragment over words and trees, presenting a complete classification of the complexity of its satisfiability problem for various navigational signatures and comparing its expressive power with other important formalisms. These include the two-variable fragment with counting and the unary negation fragment. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1093/logcom/exac002 | JOURNAL OF LOGIC AND COMPUTATION |
DocType | Volume | Issue |
Journal | 32 | 5 |
ISSN | Citations | PageRank |
0955-792X | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Emanuel Kieronski | 1 | 114 | 13.85 |
| Antti Kuusisto | 2 | 72 | 15.69 |