A1 Refereed original research article in a scientific journal
Language equations with complementation: Expressive power
Authors: Okhotin A, Yakimova O
Publisher: ELSEVIER SCIENCE BV
Publication year: 2012
Journal: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 416
First page : 71
Last page: 86
Number of pages: 16
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2011.10.003(external)
Abstract
Consider a system of language equations of the form X-i = phi(i)(X-1,...,X-n)(1 <= i <= n), where every phi(i) 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. (C) 2011 Elsevier B.V. All rights reserved.
Consider a system of language equations of the form X-i = phi(i)(X-1,...,X-n)(1 <= i <= n), where every phi(i) 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. (C) 2011 Elsevier B.V. All rights reserved.