Name
Abstract | ||
|---|---|---|
The paper gives an introduction to the problem whether there is a logic ℒ that captures PTIME in the sense that, via some natural encoding, the classes of finite structures axiomatizable in ℒ correspond to the languages in PTIME. It discusses several notions of capturing, thereby giving a picture of the general theory. The question for the most important version is still open. The paper surveys po... |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1093/jigpal/7.3.359 | Logic Journal of the IGPL |
Keywords | Field | DocType |
finite model theory,descriptive complexity,Ptime,canonization | Alternating polynomial,Discrete mathematics,Stable polynomial,Polynomial matrix,Polynomial,Monic polynomial,Reciprocal polynomial,Wilkinson's polynomial,Matrix polynomial,Mathematics | Journal |
Volume | Issue | ISSN |
7 | 3 | 1367-0751 |
Citations | PageRank | References |
1 | 0.36 | 0 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Heinz-dieter Ebbinghaus | 1 | 5 | 1.88 |