Name
Abstract | ||
|---|---|---|
We show that examinations of the expressive power of logical formulae enrichedby Lindstrom quantifiers over ordered finite structures have a well-studiedcomplexity-theoretic counterpart: the leaf language approach to define complexityclasses. Model classes of formulae with Lindstrom quantifiers are nothing elsethan leaf language definable sets. Along the way we tighten the best up to nowknown leaf language characterization of the classes of the polynomial time hierarchyand give a... |
Year | Venue | Keywords |
|---|---|---|
1998 | Int. J. Found. Comput. Sci. | expressive power,polynomial time |
DocType | Volume | Issue |
Journal | 9 | 3 |
Citations | PageRank | References |
25 | 1.11 | 13 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hans-Jörg Burtschick | 1 | 40 | 2.72 |
| Heribert Vollmer | 2 | 805 | 71.64 |