A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Solving Language Equations and Disequations with Applications to Disunification in Description Logics and Monadic Set Constraints
Tekijät: Baader F, Okhotin A
Julkaisuvuosi: 2012
Journal: Lecture Notes in Computer Science
Tietokannassa oleva lehden nimi: LOGIC FOR PROGRAMMING, ARTIFICIAL INTELLIGENCE, AND REASONING (LPAR-18)
Lehden akronyymi: LECT NOTES COMPUT SC
Vuosikerta: 7180
Aloitussivu: 107
Lopetussivu: 121
Sivujen määrä: 15
ISSN: 0302-9743
Tiivistelmä
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.
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.
Turun yliopiston Tutkimustietojärjestelmän portaali