Paper Info
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 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.
Year
DOI
Venue
2012
10.1007/978-3-642-28717-6_11
LPAR
Keywords
Field
DocType
one-sided concatenation,looping automaton,new type,monadic set constraint,boolean operation,language equation,description logic fl0,new complexity result,infinite tree,automata working
Negation,EXPTIME,System of linear equations,Computer science,Automaton,Algorithm,Description logic,Theoretical computer science,Concatenation,Tree automaton,Monad (functional programming)
Conference
Volume
ISSN
Citations 
7180
0302-9743
2
PageRank 
References 
Authors
0.36
21
2
Name
Order
Citations
PageRank
Franz Baader18123646.64
Alexander Okhotin281574.63