Complexity of Language Equations With One-Sided Concatenation and All Boolean Operations

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

Complexity of Language Equations With One-Sided Concatenation and All Boolean Operations

Franz BaaderFranz Baader,  A. OkhotinA. Okhotin
Franz Baader, A. Okhotin
Complexity of Language Equations With One-Sided Concatenation and All Boolean Operations
In Jordi Levy, eds., Proceedings of the 20th International Workshop on Unification, UNIF'06, 59-73, 2006
  • KurzfassungAbstract
    Language equations are equations where both the constants occurring in the equations and the solutions are formal languages. They have first been introduced in formal language theory, but are now also considered in other areas of computer science. In particular, they can be seen as unification problems in the algebra of languages whose operations are the Boolean operations and concatenation. They are also closely related to monadic set constraints. In the present paper, we restrict the attention to language equations with one-sided concatenation, but in contrast to previous work on these equations, we allow not just union but all Boolean operations to be used when formulating them. In addition, we are not just interested in deciding solvability of such equations, but also in deciding other properties of the set of solutions, like its cardinality (finite, infinite, uncountable) and whether it contains least/greatest solutions. We show that all these decision problems are ExpTime-complete.
  • Forschungsgruppe:Research Group: Automatentheorie
@inproceedings{ Baader-Okhotin-UNIF-06,
  author = {F. {Baader} and A. {Okhotin}},
  booktitle = {Proceedings of the 20th International Workshop on Unification, {UNIF'06}},
  editor = {Jordi {Levy}},
  pages = {59--73},
  title = {Complexity of Language Equations With One-Sided Concatenation and All {B}oolean Operations},
  year = {2006},
}