Unresolved systems of language equations: Expressive power and decision problems
详细信息 查看全文
- 作者：Alexander Okhotin
- 关键词：Formal languages ; Language equations ; Decision problems
- 刊名：Theoretical Computer Science
- 出版年：2005
- 出版时间：16 December 2005
- 年：2005
- 卷：349
- 期：3
- 页码：283-308
- 全文大小：391 K
文摘
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 ujXijvj