Name
Title | ||
|---|---|---|
Two-variable logics with some betweenness relations: Expressiveness, satisfiability and membership. |
Abstract | ||
|---|---|---|
study two extensions of FO2[u003c], first-order logic interpreted in finite words, in which formulas are restricted to use only two variables. adjoin to this language two-variable atomic formulas that say, `the letter a appears between positions x and yu0027 and `the factor u appears between positions x and yu0027. These are, in a sense, the simplest properties that are not expressible using only two variables. We present several logics, both first-order and temporal, that have the same expressive power, and find matching lower and upper bounds for the complexity of satisfiability for each of these formulations. give effective conditions, in terms of the syntactic monoid of a regular language, for a property to be expressible in these logics. This algebraic analysis allows us to prove, among other things, that our new logics have strictly less expressive power than full first-order logic FO[u003c]. Our proofs required the development of novel techniques concerning factorizations of words. |
Year | Venue | DocType |
|---|---|---|
2019 | arXiv: Logic in Computer Science | Journal |
Volume | Issue | Citations |
abs/1902.05905 | 3 | 0 |
PageRank | References | Authors |
0.34 | 10 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andreas Krebs | 1 | 21 | 8.20 |
| Kamal Lodaya | 2 | 225 | 19.53 |
| Paritosh K. Pandya | 3 | 944 | 91.64 |
| Howard Straubing | 4 | 528 | 60.92 |