A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Language equations with complementation: Expressive power
Tekijät: Okhotin A, Yakimova O
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2012
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 416
Aloitussivu: 71
Lopetussivu: 86
Sivujen määrä: 16
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2011.10.003
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali