Standard
On the expressive power of GF(2)-grammars. / Makarov, Vladislav; Okhotin, Alexander.
SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. ред. / Rastislav Královič; Giovanni Pighizzini; Jerzy Nawrocki; Barbara Catania. Springer Nature, 2019. стр. 310-323 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11376 LNCS).
Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Harvard
Makarov, V
& Okhotin, A 2019,
On the expressive power of GF(2)-grammars. в R Královič, G Pighizzini, J Nawrocki & B Catania (ред.),
SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 11376 LNCS, Springer Nature, стр. 310-323, 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018, Nový Smokovec, Словакия,
27/01/19.
https://doi.org/10.1007/978-3-030-10801-4_25APA
Makarov, V.
, & Okhotin, A. (2019).
On the expressive power of GF(2)-grammars. в R. Královič, G. Pighizzini, J. Nawrocki, & B. Catania (Ред.),
SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings (стр. 310-323). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11376 LNCS). Springer Nature.
https://doi.org/10.1007/978-3-030-10801-4_25Vancouver
Makarov V
, Okhotin A.
On the expressive power of GF(2)-grammars. в Královič R, Pighizzini G, Nawrocki J, Catania B, Редакторы, SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Springer Nature. 2019. стр. 310-323. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
https://doi.org/10.1007/978-3-030-10801-4_25Author
Makarov, Vladislav
; Okhotin, Alexander. /
On the expressive power of GF(2)-grammars. SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Редактор / Rastislav Královič ; Giovanni Pighizzini ; Jerzy Nawrocki ; Barbara Catania. Springer Nature, 2019. стр. 310-323 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{af6a05a7d98641af8aac4836c589b256,
title = "On the expressive power of GF(2)-grammars",
abstract = "GF(2)-grammars, recently introduced by Bakinova et al. (“ Formal languages over GF(2) ”, LATA 2018), are a variant of ordinary context-free grammars, in which the disjunction is replaced by exclusive OR, whereas the classical concatenation is replaced by a new operation called GF(2)-concatenation: KʘL is the set of all strings with an odd number of partitions into a concatenation of a string in K and a string in L. This paper establishes several results on the family of languages defined by these grammars. Over the unary alphabet, GF(2)-grammars define exactly the 2-automatic sets. No language of the form (formula Presented), with uniformly superlinear f, can be described by any GF(2)-grammar. The family is not closed under union, intersection, classical concatenation and Kleene star, non-erasing homomorphisms. On the other hand, this family is closed under injective nondeterministic finite transductions, and contains a hardest language under reductions by homomorphisms.",
author = "Vladislav Makarov and Alexander Okhotin",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-10801-4_25",
language = "English",
isbn = "9783030108007",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "310--323",
editor = "Rastislav Kr{\'a}lovi{\v c} and Giovanni Pighizzini and Jerzy Nawrocki and Barbara Catania",
booktitle = "SOFSEM 2019",
address = "Germany",
note = "45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 ; Conference date: 27-01-2019 Through 30-01-2019",
}
RIS
TY - GEN
T1 - On the expressive power of GF(2)-grammars
AU - Makarov, Vladislav
AU - Okhotin, Alexander
PY - 2019/1/1
Y1 - 2019/1/1
N2 - GF(2)-grammars, recently introduced by Bakinova et al. (“ Formal languages over GF(2) ”, LATA 2018), are a variant of ordinary context-free grammars, in which the disjunction is replaced by exclusive OR, whereas the classical concatenation is replaced by a new operation called GF(2)-concatenation: KʘL is the set of all strings with an odd number of partitions into a concatenation of a string in K and a string in L. This paper establishes several results on the family of languages defined by these grammars. Over the unary alphabet, GF(2)-grammars define exactly the 2-automatic sets. No language of the form (formula Presented), with uniformly superlinear f, can be described by any GF(2)-grammar. The family is not closed under union, intersection, classical concatenation and Kleene star, non-erasing homomorphisms. On the other hand, this family is closed under injective nondeterministic finite transductions, and contains a hardest language under reductions by homomorphisms.
AB - GF(2)-grammars, recently introduced by Bakinova et al. (“ Formal languages over GF(2) ”, LATA 2018), are a variant of ordinary context-free grammars, in which the disjunction is replaced by exclusive OR, whereas the classical concatenation is replaced by a new operation called GF(2)-concatenation: KʘL is the set of all strings with an odd number of partitions into a concatenation of a string in K and a string in L. This paper establishes several results on the family of languages defined by these grammars. Over the unary alphabet, GF(2)-grammars define exactly the 2-automatic sets. No language of the form (formula Presented), with uniformly superlinear f, can be described by any GF(2)-grammar. The family is not closed under union, intersection, classical concatenation and Kleene star, non-erasing homomorphisms. On the other hand, this family is closed under injective nondeterministic finite transductions, and contains a hardest language under reductions by homomorphisms.
UR - http://www.scopus.com/inward/record.url?scp=85062357069&partnerID=8YFLogxK
UR - http://www.mendeley.com/research/expressive-power-gf2grammars
U2 - 10.1007/978-3-030-10801-4_25
DO - 10.1007/978-3-030-10801-4_25
M3 - Conference contribution
AN - SCOPUS:85062357069
SN - 9783030108007
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 310
EP - 323
BT - SOFSEM 2019
A2 - Královič, Rastislav
A2 - Pighizzini, Giovanni
A2 - Nawrocki, Jerzy
A2 - Catania, Barbara
PB - Springer Nature
T2 - 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018
Y2 - 27 January 2019 through 30 January 2019
ER -
