TY - JOUR

T1 - On language equations with one-sided concatenation

AU - Baader, Franz

AU - Okhotin, Alexander

PY - 2013/11/25

Y1 - 2013/11/25

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

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

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

U2 - 10.3233/FI-2013-870

DO - 10.3233/FI-2013-870

M3 - Article

AN - SCOPUS:84887890177

VL - 126

SP - 1

EP - 35

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 1

ER -