Standard

Language equations with complementation : Decision problems. / Okhotin, Alexander; Yakimova, Oksana.

в: Theoretical Computer Science, Том 376, № 1-2, 10.05.2007, стр. 112-126.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Okhotin, A & Yakimova, O 2007, 'Language equations with complementation: Decision problems', Theoretical Computer Science, Том. 376, № 1-2, стр. 112-126. https://doi.org/10.1016/j.tcs.2007.01.016

APA

Okhotin, A., & Yakimova, O. (2007). Language equations with complementation: Decision problems. Theoretical Computer Science, 376(1-2), 112-126. https://doi.org/10.1016/j.tcs.2007.01.016

Vancouver

Okhotin A, Yakimova O. Language equations with complementation: Decision problems. Theoretical Computer Science. 2007 Май 10;376(1-2):112-126. https://doi.org/10.1016/j.tcs.2007.01.016

Author

Okhotin, Alexander ; Yakimova, Oksana. / Language equations with complementation : Decision problems. в: Theoretical Computer Science. 2007 ; Том 376, № 1-2. стр. 112-126.

BibTeX

@article{17b7ccaecd2c4ae1b78a1a6ad3e8ba86,
title = "Language equations with complementation: Decision problems",
abstract = "Systems of language equations of the form Xi = φi (X1, ..., Xn) (1 ≤ i ≤ n) are studied. Here every φi may contain the operations of concatenation and complementation. The properties of having solutions and of having a unique solution are given mathematical characterizations. As decision problems, the former is NP-complete, while the latter is PSPACE-hard and is in co-RE, and its decidability remains, in general, open. Uniqueness becomes decidable in the case of a unary alphabet, where it is US-complete, and in the case of linear concatenation, where it is L-complete.",
keywords = "Complementation, Computational complexity, Decision problems, Language equations, Negation",
author = "Alexander Okhotin and Oksana Yakimova",
year = "2007",
month = may,
day = "10",
doi = "10.1016/j.tcs.2007.01.016",
language = "English",
volume = "376",
pages = "112--126",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "1-2",

}

RIS

TY - JOUR

T1 - Language equations with complementation

T2 - Decision problems

AU - Okhotin, Alexander

AU - Yakimova, Oksana

PY - 2007/5/10

Y1 - 2007/5/10

N2 - Systems of language equations of the form Xi = φi (X1, ..., Xn) (1 ≤ i ≤ n) are studied. Here every φi may contain the operations of concatenation and complementation. The properties of having solutions and of having a unique solution are given mathematical characterizations. As decision problems, the former is NP-complete, while the latter is PSPACE-hard and is in co-RE, and its decidability remains, in general, open. Uniqueness becomes decidable in the case of a unary alphabet, where it is US-complete, and in the case of linear concatenation, where it is L-complete.

AB - Systems of language equations of the form Xi = φi (X1, ..., Xn) (1 ≤ i ≤ n) are studied. Here every φi may contain the operations of concatenation and complementation. The properties of having solutions and of having a unique solution are given mathematical characterizations. As decision problems, the former is NP-complete, while the latter is PSPACE-hard and is in co-RE, and its decidability remains, in general, open. Uniqueness becomes decidable in the case of a unary alphabet, where it is US-complete, and in the case of linear concatenation, where it is L-complete.

KW - Complementation

KW - Computational complexity

KW - Decision problems

KW - Language equations

KW - Negation

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

U2 - 10.1016/j.tcs.2007.01.016

DO - 10.1016/j.tcs.2007.01.016

M3 - Article

AN - SCOPUS:34247164397

VL - 376

SP - 112

EP - 126

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1-2

ER -

ID: 41141424