LATPub495: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
| (2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 9: | Zeile 9: | ||
|Year=2012 | |Year=2012 | ||
|Month= | |Month= | ||
|Booktitle=Proceedings of the 18th International Conference on Logic for Programming, Artifical Intelligence, and Reasoning | |Booktitle=Proceedings of the 18th International Conference on Logic for Programming, Artifical Intelligence, and Reasoning (LPAR-12) | ||
|Editor=Nikolaj | |Editor=Nikolaj Bjørner and Andrei Voronkov | ||
|Note= | |Note= | ||
|Organization= | |Organization= | ||
|Pages=107 | |Pages=107-121 | ||
|Publisher=Springer | |Publisher=Springer | ||
|Series=Lecture Notes in Computer Science | |Series=Lecture Notes in Computer Science | ||
| Zeile 20: | Zeile 20: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=We extend previous results on the complexity of solving language equations with one-sided | |Abstract=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 FL0 and for monadic set constraints with negation. We believe that looping automata with colors may also turn out to be useful in other applications. | ||
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 FL0 and for monadic set constraints | |||
with negation. We believe that looping automata with colors may also turn out to be useful | |||
in other applications. | |||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 49: | Zeile 41: | ||
year = {2012}, | year = {2012}, | ||
} | } | ||
}} | }} | ||
Aktuelle Version vom 25. März 2015, 16:34 Uhr
Solving language equations and disequations with applications to disunification in description logics and monadic set constraints
Franz BaaderFranz Baader, Alexander OkhotinAlexander Okhotin
Franz Baader, Alexander Okhotin
Solving language equations and disequations with applications to disunification in description logics and monadic set constraints
In Nikolaj Bjørner and Andrei Voronkov, eds., Proceedings of the 18th International Conference on Logic for Programming, Artifical Intelligence, and Reasoning (LPAR-12), volume 7180 of Lecture Notes in Computer Science, 107-121, 2012. Springer
Solving language equations and disequations with applications to disunification in description logics and monadic set constraints
In Nikolaj Bjørner and Andrei Voronkov, eds., Proceedings of the 18th International Conference on Logic for Programming, Artifical Intelligence, and Reasoning (LPAR-12), volume 7180 of Lecture Notes in Computer Science, 107-121, 2012. Springer
- KurzfassungAbstract
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 FL0 and for monadic set constraints with negation. We believe that looping automata with colors may also turn out to be useful in other applications. - Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ BaOk-LPAR18,
address = {M{\'e}rida, Venezuela},
author = {Franz {Baader} and Alexander {Okhotin}},
booktitle = {Proceedings of the 18th International Conference on Logic for Programming, Artifical Intelligence, and Reasoning {(LPAR-12)}},
editor = {Nikolaj {Bj{\o}rner} and Andrei {Voronkov}},
pages = {107--121},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
title = {Solving language equations and disequations with applications to disunification in description logics and monadic set constraints},
volume = {7180},
year = {2012},
}
