- Titel
- Solving Language Equations and Disequations Using Looping Tree Automata with Colors
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-795272
- Schriftenreihe
- LTCS-Report
- Bandnummer
- 12-01
- Erstveröffentlichung
- 2012
- DOI
- https://doi.org/10.25368/2022.185
- Abstract (EN)
- We extend previous results on the complexity of solving language equations with one-sided concatenation and all Boolean operations to the case where also disequations (i.e., negated equations) may occur. To show that solvability of systems of equations and disequations is still in ExpTime, we introduce a new type of automata working on infinite trees, which we call looping automata with colors. As applications of these results, we show new complexity results for disunification in the description logic FL₀ and for monadic set constraints with negation. We believe that looping automata with colors may also turn out to be useful in other applications.
- A short version of this report has also appeared in Proceedings of LPAR-18, Springer LNCS 7180, 2012.
- Freie Schlagwörter (DE)
- Subsumtion, Gleichung, Ungleichung, Beschreibungslogik
- Freie Schlagwörter (EN)
- subsumption, equation, disequation, description logic
- Klassifikation (DDC)
- 004
- Klassifikation (RVK)
- ST 136
- Publizierende Institution
- Technische Universität Dresden, Dresden
- Version / Begutachtungsstatus
- angenommene Version / Postprint / Autorenversion
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa2-795272
- Veröffentlichungsdatum Qucosa
- 16.06.2022
- Dokumenttyp
- Bericht
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
CC BY 4.0