Language equations with complementation: Expressive power

详细信息    查看全文

• 作者：Alexander Okhotin^a ; ^b ; ^{alexander.okhotin@utu.fi} ; Oksana Yakimova^c ; ¹ ; ^{yakimova@mpim-bonn.mpg.de}
• 关键词：Language equations ; Complementation ; Negation ; Boolean grammars ; Context-free grammars
• 刊名：Theoretical Computer Science
• 出版年：2012
• 出版时间：27 January 2012
• 年：2012
• 卷：416
• 期：Complete
• 页码：71-86
• 全文大小：448 K

文摘

Consider a system of language equations of the form , where every may contain the operations of concatenation and complementation. These systems have been studied in ¡°Language equations with complementation: Decision problems?[A. Okhotin, O. Yakimova, Theoretical Computer Science 376 (2007) 112-126]. This paper investigates the family of languages representable by unique solutions of such systems. A method for proving nonrepresentability of particular languages is developed. Several natural subfamilies of this family are compared to each other and to the main known families of formal languages. Their position in the hierarchy is established.