| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4663009 | Journal of Applied Logic | 2012 | 8 Pages |
Abstract
We give a new construction of formulas in Hanf normal form that are equivalent to first-order formulas over structures of bounded degree. This is the first algorithm whose running time is shown to be elementary. The triply exponential upper bound is complemented by a matching lower bound.
Related Topics
Physical Sciences and Engineering
Mathematics
Logic
Authors
Benedikt Bollig, Dietrich Kuske,