Solving language equations and disequations with applications to disunification in description logics and monadic set constraints

Franz Baader, Alexander Okhotin

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференции

5 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииLogic for Programming, Artificial Intelligence, and Reasoning - 18th International Conference, LPAR-18, Proceedings
Страницы107-121
Число страниц15
DOI
СостояниеОпубликовано - 21 мар 2012
Событие18th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR-18 - Merida, Боливарианская Республика Венесуэла
Продолжительность: 11 мар 201215 мар 2012

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том7180 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция18th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR-18
СтранаБоливарианская Республика Венесуэла
ГородMerida
Период11/03/1215/03/12

Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

Fingerprint Подробные сведения о темах исследования «Solving language equations and disequations with applications to disunification in description logics and monadic set constraints». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать