Standard

Solving language equations and disequations with applications to disunification in description logics and monadic set constraints. / Baader, Franz; Okhotin, Alexander.

Logic for Programming, Artificial Intelligence, and Reasoning - 18th International Conference, LPAR-18, Proceedings. 2012. p. 107-121 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7180 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Baader, F & Okhotin, A 2012, Solving language equations and disequations with applications to disunification in description logics and monadic set constraints. in Logic for Programming, Artificial Intelligence, and Reasoning - 18th International Conference, LPAR-18, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7180 LNCS, pp. 107-121, 18th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR-18, Merida, Venezuela, Bolivarian Republic of, 11/03/12. https://doi.org/10.1007/978-3-642-28717-6_11

APA

Baader, F., & Okhotin, A. (2012). Solving language equations and disequations with applications to disunification in description logics and monadic set constraints. In Logic for Programming, Artificial Intelligence, and Reasoning - 18th International Conference, LPAR-18, Proceedings (pp. 107-121). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7180 LNCS). https://doi.org/10.1007/978-3-642-28717-6_11

Vancouver

Baader F, Okhotin A. Solving language equations and disequations with applications to disunification in description logics and monadic set constraints. In Logic for Programming, Artificial Intelligence, and Reasoning - 18th International Conference, LPAR-18, Proceedings. 2012. p. 107-121. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-28717-6_11

Author

Baader, Franz ; Okhotin, Alexander. / Solving language equations and disequations with applications to disunification in description logics and monadic set constraints. Logic for Programming, Artificial Intelligence, and Reasoning - 18th International Conference, LPAR-18, Proceedings. 2012. pp. 107-121 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{6f43548842974c3aa6fa774f4a425cd6,
title = "Solving language equations and disequations with applications to disunification in description logics and monadic set constraints",
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 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.",
author = "Franz Baader and Alexander Okhotin",
year = "2012",
month = mar,
day = "21",
doi = "10.1007/978-3-642-28717-6_11",
language = "English",
isbn = "9783642287169",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "107--121",
booktitle = "Logic for Programming, Artificial Intelligence, and Reasoning - 18th International Conference, LPAR-18, Proceedings",
note = "18th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR-18 ; Conference date: 11-03-2012 Through 15-03-2012",

}

RIS

TY - GEN

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

AU - Baader, Franz

AU - Okhotin, Alexander

PY - 2012/3/21

Y1 - 2012/3/21

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84858316724&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-28717-6_11

DO - 10.1007/978-3-642-28717-6_11

M3 - Conference contribution

AN - SCOPUS:84858316724

SN - 9783642287169

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 107

EP - 121

BT - Logic for Programming, Artificial Intelligence, and Reasoning - 18th International Conference, LPAR-18, Proceedings

T2 - 18th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR-18

Y2 - 11 March 2012 through 15 March 2012

ER -

ID: 41139765