Standard

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

Developments in Language Theory - 10th International Conference, DLT 2006, Proceedings. Springer Nature, 2006. p. 420-432 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4036 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Okhotin, A & Yakimova, O 2006, Language equations with complementation. in Developments in Language Theory - 10th International Conference, DLT 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4036 LNCS, Springer Nature, pp. 420-432, 10th International Conference on Developments in Language Theory, DLT 2006, Santa Barbara, CA, United States, 26/06/06. https://doi.org/10.1007/11779148_38

APA

Okhotin, A., & Yakimova, O. (2006). Language equations with complementation. In Developments in Language Theory - 10th International Conference, DLT 2006, Proceedings (pp. 420-432). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4036 LNCS). Springer Nature. https://doi.org/10.1007/11779148_38

Vancouver

Okhotin A, Yakimova O. Language equations with complementation. In Developments in Language Theory - 10th International Conference, DLT 2006, Proceedings. Springer Nature. 2006. p. 420-432. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11779148_38

Author

Okhotin, Alexander ; Yakimova, Oksana. / Language equations with complementation. Developments in Language Theory - 10th International Conference, DLT 2006, Proceedings. Springer Nature, 2006. pp. 420-432 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{0ff0f42750c344d1b594a4a15adf0f7c,
title = "Language equations with complementation",
abstract = "Systems of language equations of the form Xi = φi(X1,..., Xn) (1 ≤ t ≤ n) are studied, in which 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 in co-RE and its decidability remains, in general, open. Uniqueness becomes decidable for a unary alphabet, where it is US-complete, and in the case of linear concatenation, where it is L-complete. The position of the languages defined by these equations in the hierarchy of language families is established.",
author = "Alexander Okhotin and Oksana Yakimova",
year = "2006",
month = jan,
day = "1",
doi = "10.1007/11779148_38",
language = "English",
isbn = "354035428X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "420--432",
booktitle = "Developments in Language Theory - 10th International Conference, DLT 2006, Proceedings",
address = "Germany",
note = "10th International Conference on Developments in Language Theory, DLT 2006 ; Conference date: 26-06-2006 Through 29-06-2006",

}

RIS

TY - GEN

T1 - Language equations with complementation

AU - Okhotin, Alexander

AU - Yakimova, Oksana

PY - 2006/1/1

Y1 - 2006/1/1

N2 - Systems of language equations of the form Xi = φi(X1,..., Xn) (1 ≤ t ≤ n) are studied, in which 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 in co-RE and its decidability remains, in general, open. Uniqueness becomes decidable for a unary alphabet, where it is US-complete, and in the case of linear concatenation, where it is L-complete. The position of the languages defined by these equations in the hierarchy of language families is established.

AB - Systems of language equations of the form Xi = φi(X1,..., Xn) (1 ≤ t ≤ n) are studied, in which 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 in co-RE and its decidability remains, in general, open. Uniqueness becomes decidable for a unary alphabet, where it is US-complete, and in the case of linear concatenation, where it is L-complete. The position of the languages defined by these equations in the hierarchy of language families is established.

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

U2 - 10.1007/11779148_38

DO - 10.1007/11779148_38

M3 - Conference contribution

AN - SCOPUS:33746210775

SN - 354035428X

SN - 9783540354284

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 420

EP - 432

BT - Developments in Language Theory - 10th International Conference, DLT 2006, Proceedings

PB - Springer Nature

T2 - 10th International Conference on Developments in Language Theory, DLT 2006

Y2 - 26 June 2006 through 29 June 2006

ER -

ID: 41144089