On the role of complementation in implicit language equations and relations

详细信息    查看全文

• 作者：Adrian Ionescu ; Ernst L. Leiss
• 关键词：Languages ; Equations ; Relations ; Implicit ; Complementation
• 刊名：Journal of Computer and System Sciences
• 出版年：March, 2014
• 年：2014
• 卷：80
• 期：2
• 页码：457-467
• 全文大小：227 K

文摘

We solve systems of boolean implicit equations and relations with union and complementation. If the languages are regular, we determine whether a system of implicit boolean equations or relations has solutions. If there is a solution, we provide an effective construction of a (regular) solution. We give representations for maximal and minimal solutions. Moreover, we also solve the problem of uniqueness of solutions as well as whether infinitely many solutions exist.