Standard

Language equations with complementation : Expressive power. / Okhotin, Alexander; Yakimova, Oksana.

In: Theoretical Computer Science, Vol. 416, 27.01.2012, p. 71-86.

Research output: Contribution to journal › Article › peer-review

Harvard

Okhotin, A & Yakimova, O 2012, 'Language equations with complementation: Expressive power', Theoretical Computer Science, vol. 416, pp. 71-86. https://doi.org/10.1016/j.tcs.2011.10.003

APA

Okhotin, A., & Yakimova, O. (2012). Language equations with complementation: Expressive power. Theoretical Computer Science, 416, 71-86. https://doi.org/10.1016/j.tcs.2011.10.003

Vancouver

Okhotin A, Yakimova O. Language equations with complementation: Expressive power. Theoretical Computer Science. 2012 Jan 27;416:71-86. https://doi.org/10.1016/j.tcs.2011.10.003

Author

Okhotin, Alexander ; Yakimova, Oksana. / Language equations with complementation : Expressive power. In: Theoretical Computer Science. 2012 ; Vol. 416. pp. 71-86.

BibTeX

@article{98ec93c19a0e4d05b86969302fea5802,
title = "Language equations with complementation: Expressive power",
abstract = "Consider a system of language equations of the form Xi= φi( X1,..., Xn)(1in), where every φ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) 112126]. 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.",
keywords = "Boolean grammars, Complementation, Context-free grammars, Language equations, Negation",
author = "Alexander Okhotin and Oksana Yakimova",
year = "2012",
month = jan,
day = "27",
doi = "10.1016/j.tcs.2011.10.003",
language = "English",
volume = "416",
pages = "71--86",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Language equations with complementation

T2 - Expressive power

AU - Okhotin, Alexander

AU - Yakimova, Oksana

PY - 2012/1/27

Y1 - 2012/1/27

N2 - Consider a system of language equations of the form Xi= φi( X1,..., Xn)(1in), where every φ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) 112126]. 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.

AB - Consider a system of language equations of the form Xi= φi( X1,..., Xn)(1in), where every φ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) 112126]. 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.

KW - Boolean grammars

KW - Complementation

KW - Context-free grammars

KW - Language equations

KW - Negation

UR - http://www.scopus.com/inward/record.url?scp=84855456631&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2011.10.003

DO - 10.1016/j.tcs.2011.10.003

M3 - Article

AN - SCOPUS:84855456631

VL - 416

SP - 71

EP - 86

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -

ID: 41140000