TY - JOUR

T1 - Unresolved systems of language equations

T2 - Expressive power and decision problems

AU - Okhotin, Alexander

PY - 2005/12/16

Y1 - 2005/12/16

N2 - Unresolved language equations and inequalities with various sets of operations are considered. It is proved that systems of unresolved equations with linear concatenation and union only, as well as systems with linear concatenation and intersection only, are as expressive as the more general unresolved inequalities with all Boolean operations and unrestricted concatenation: the class of languages defined by unique (least, greatest) solutions of these systems is shown to coincide with the families of recursive (RE, co-RE, resp.) sets, which result extends even to individual equations of the form x∪ujXijvj=w∪x∪yjXtjzj. On the other hand, unresolved equations with different sets of operations are shown to differ in the hardness of their decision problems, and it is demonstrated that several types of unresolved equations cannot effectively simulate each other in spite of the equality of the language families they define.

AB - Unresolved language equations and inequalities with various sets of operations are considered. It is proved that systems of unresolved equations with linear concatenation and union only, as well as systems with linear concatenation and intersection only, are as expressive as the more general unresolved inequalities with all Boolean operations and unrestricted concatenation: the class of languages defined by unique (least, greatest) solutions of these systems is shown to coincide with the families of recursive (RE, co-RE, resp.) sets, which result extends even to individual equations of the form x∪ujXijvj=w∪x∪yjXtjzj. On the other hand, unresolved equations with different sets of operations are shown to differ in the hardness of their decision problems, and it is demonstrated that several types of unresolved equations cannot effectively simulate each other in spite of the equality of the language families they define.

KW - Decision problems

KW - Formal languages

KW - Language equations

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

U2 - 10.1016/j.tcs.2005.07.038

DO - 10.1016/j.tcs.2005.07.038

M3 - Article

AN - SCOPUS:27844494750

VL - 349

SP - 283

EP - 308

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 3

ER -