Name
Abstract | ||
|---|---|---|
We consider fragments of first-order logic over finite words. In particular, we deal with first-order logic with a restricted number of variables and with the lower levels of the alternation hierarchy. We use the algebraic approach to show decidability of expressibility within these fragments. As a byproduct, we survey several characterizations of the respective fragments. We give complete proofs for all characterizations and we provide all necessary background. Some of the proofs seem to be new and simpler than those which can be found elsewhere. We also give a proof of Simon's theorem on factorization forests restricted to aperiodic monoids because this is simpler and sufficient for our purpose. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1142/S0129054108005802 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
first-order logic, monoids, factorization forests, piecewise-testable languages | Discrete mathematics,Combinatorics,Algebraic number,Algebra,Decidability,First-order logic,Monoid,Mathematical proof,Factorization,Aperiodic graph,Mathematics,Alternation (linguistics) | Journal |
Volume | Issue | ISSN |
19 | 3 | 0129-0541 |
Citations | PageRank | References |
35 | 1.34 | 51 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Volker Diekert | 1 | 702 | 67.46 |
| Paul Gastin | 2 | 1165 | 75.66 |
| Manfred Kufleitner | 3 | 171 | 21.00 |