- Titel
- Complementation and Inclusion of Weighted Automata on Infinite Trees
- Untertitel
- Revised Version
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-795229
- Schriftenreihe
- LTCS-Report
- Bandnummer
- 11-02
- Erstveröffentlichung
- 2011
- DOI
- https://doi.org/10.25368/2022.180
- Abstract (EN)
- Weighted automata can be seen as a natural generalization of finite state automata to more complex algebraic structures. The standard reasoning tasks for unweighted automata can also be generalized to the weighted setting. In this report we study the problems of intersection, complementation, and inclusion for weighted automata on infinite trees and show that they are not harder complexity-wise than reasoning with unweighted automata. We also present explicit methods for solving these problems optimally.
- Freie Schlagwörter (DE)
- gewichteter Automat, Beschreibungslogik, Satz von Kruskal
- Freie Schlagwörter (EN)
- weighted automaton, description logic, Kruskal´s tree theorem
- 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-795229
- Veröffentlichungsdatum Qucosa
- 16.06.2022
- Dokumenttyp
- Bericht
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
CC BY 4.0