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 languageEnglish
Title of host publicationLogic for Programming, Artificial Intelligence, and Reasoning - 18th International Conference, LPAR-18, Proceedings
Pages107-121
Number of pages15
DOIs
StatePublished - 21 Mar 2012
Event18th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR-18 - Merida, Venezuela, Bolivarian Republic of
Duration: 11 Mar 201215 Mar 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7180 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR-18
Country/TerritoryVenezuela, Bolivarian Republic of
CityMerida
Period11/03/1215/03/12

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 41139765