Preservation and decomposition theorems for bounded degree structures
- We provide elementary algorithms for two preservation theorems for first-order sentences (FO) on the class ℭd of all finite structures of degree at most d: For each FO-sentence that is preserved under extensions (homomorphisms) on ℭd, a ℭd-equivalent existential (existential-positive) FO-sentence can be constructed in 5-fold (4-fold) exponential time. This is complemented by lower bounds showing that a 3-fold exponential blow-up of the computed existential (existential-positive) sentence is unavoidable. Both algorithms can be extended (while maintaining the upper and lower bounds on their time complexity) to input first-order sentences with modulo m counting quantifiers (FO+MODm). Furthermore, we show that for an input FO-formula, a ℭd-equivalent Feferman-Vaught decomposition can be computed in 3-fold exponential time. We also provide a matching lower bound
| Verfasserangaben: | Frederik Harwath, Lucas Heimberg, Nicole Schweikardt |
|---|---|
| URN: | urn:nbn:de:hebis:30:3-306349 |
| DOI: | https://doi.org/10.2168/LMCS-11(4:17)2015 |
| ISSN: | 1860-5974 |
| ArXiv-Id: | http://arxiv.org/abs/1511.05888 |
| Titel des übergeordneten Werkes (Deutsch): | Logical Methods in Computer Science |
| Verlag: | Department of Theoretical Computer Science, Technical University of Braunschweig |
| Verlagsort: | Braunschweig |
| Dokumentart: | Wissenschaftlicher Artikel |
| Sprache: | Englisch |
| Datum der Veröffentlichung (online): | 29.12.2015 |
| Datum der Erstveröffentlichung: | 29.12.2015 |
| Veröffentlichende Institution: | Universitätsbibliothek Johann Christian Senckenberg |
| Datum der Freischaltung: | 16.06.2016 |
| Jahrgang: | 11 |
| Ausgabe / Heft: | 4:17 |
| Seitenzahl: | 44 |
| Erste Seite: | 1 |
| Letzte Seite: | 44 |
| Bemerkung: | Creative Commons http://creativecommons.org/licenses/by-nd/2.0/ |
| HeBIS-PPN: | 425322963 |
| Institute: | Informatik und Mathematik / Informatik |
| DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
| Sammlungen: | Universitätspublikationen |
| Lizenz (Deutsch): |  Creative Commons - Namensnennung-Keine Bearbeitung |
