Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
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 0 and for monadic set constraints with negation. We believe that looping automata with colors may also turn out to be useful in other applications.
Original language | English |
---|---|
Title of host publication | Logic for Programming, Artificial Intelligence, and Reasoning - 18th International Conference, LPAR-18, Proceedings |
Pages | 107-121 |
Number of pages | 15 |
DOIs | |
State | Published - 21 Mar 2012 |
Event | 18th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR-18 - Merida, Venezuela, Bolivarian Republic of Duration: 11 Mar 2012 → 15 Mar 2012 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 7180 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 18th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR-18 |
---|---|
Country/Territory | Venezuela, Bolivarian Republic of |
City | Merida |
Period | 11/03/12 → 15/03/12 |
ID: 41139765