Standard
Language equations with symmetric difference. / Okhotin, Alexander.
Computer Science - Theory and Applications, First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings. ред. / Dima Grigoriev; John Harrison; Edward A. Hirsch. Том 3967 LNCS 2006. стр. 292-303 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Harvard
Okhotin, A 2006,
Language equations with symmetric difference. в D Grigoriev, J Harrison & EA Hirsch (ред.),
Computer Science - Theory and Applications, First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings. Том. 3967 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), стр. 292-303, 1st International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Российская Федерация,
8/06/06.
https://doi.org/10.1007/11753728_30
APA
Okhotin, A. (2006).
Language equations with symmetric difference. в D. Grigoriev, J. Harrison, & E. A. Hirsch (Ред.),
Computer Science - Theory and Applications, First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings (Том 3967 LNCS, стр. 292-303). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
https://doi.org/10.1007/11753728_30
Vancouver
Okhotin A.
Language equations with symmetric difference. в Grigoriev D, Harrison J, Hirsch EA, Редакторы, Computer Science - Theory and Applications, First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings. Том 3967 LNCS. 2006. стр. 292-303. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
https://doi.org/10.1007/11753728_30
Author
Okhotin, Alexander. /
Language equations with symmetric difference. Computer Science - Theory and Applications, First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings. Редактор / Dima Grigoriev ; John Harrison ; Edward A. Hirsch. Том 3967 LNCS 2006. стр. 292-303 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{39b10d096a9b4847b95eebad2ee241c2,
title = "Language equations with symmetric difference",
abstract = "Systems of language equations used by Ginsburg and Rice ({"}Two families of languages related to ALGOL{"}, JACM, 1962) to represent context-free grammars are modified to use the symmetric difference operation instead of union. Contrary to a natural expectation that these two types of equations should have incomparable expressive power, it is shown that equations with symmetric difference can express every recursive set by their unique solutions, every recursively enumerable set by their least solutions and every co-recursively-enumerable set by their greatest solutions. The solution existence problem is II1-complete, the existence of a unique, a least or a greatest solution is ∏2-complete, while the existence of finitely many solutions is Σ3-complete.",
author = "Alexander Okhotin",
year = "2006",
doi = "10.1007/11753728_30",
language = "English",
volume = "3967 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "292--303",
editor = "Dima Grigoriev and John Harrison and Hirsch, {Edward A.}",
booktitle = "Computer Science - Theory and Applications, First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings",
note = "1st International Computer Science Symposium in Russia, CSR 2006 ; Conference date: 08-06-2006 Through 12-06-2006",
}
RIS
TY - GEN
T1 - Language equations with symmetric difference
AU - Okhotin, Alexander
PY - 2006
Y1 - 2006
N2 - Systems of language equations used by Ginsburg and Rice ("Two families of languages related to ALGOL", JACM, 1962) to represent context-free grammars are modified to use the symmetric difference operation instead of union. Contrary to a natural expectation that these two types of equations should have incomparable expressive power, it is shown that equations with symmetric difference can express every recursive set by their unique solutions, every recursively enumerable set by their least solutions and every co-recursively-enumerable set by their greatest solutions. The solution existence problem is II1-complete, the existence of a unique, a least or a greatest solution is ∏2-complete, while the existence of finitely many solutions is Σ3-complete.
AB - Systems of language equations used by Ginsburg and Rice ("Two families of languages related to ALGOL", JACM, 1962) to represent context-free grammars are modified to use the symmetric difference operation instead of union. Contrary to a natural expectation that these two types of equations should have incomparable expressive power, it is shown that equations with symmetric difference can express every recursive set by their unique solutions, every recursively enumerable set by their least solutions and every co-recursively-enumerable set by their greatest solutions. The solution existence problem is II1-complete, the existence of a unique, a least or a greatest solution is ∏2-complete, while the existence of finitely many solutions is Σ3-complete.
UR - http://www.scopus.com/inward/record.url?scp=33745924141&partnerID=8YFLogxK
U2 - 10.1007/11753728_30
DO - 10.1007/11753728_30
M3 - Conference contribution
AN - SCOPUS:33745924141
VL - 3967 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 292
EP - 303
BT - Computer Science - Theory and Applications, First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings
A2 - Grigoriev, Dima
A2 - Harrison, John
A2 - Hirsch, Edward A.
T2 - 1st International Computer Science Symposium in Russia, CSR 2006
Y2 - 8 June 2006 through 12 June 2006
ER -
