DOI

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.

Язык оригиналаанглийский
Название основной публикации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
Страницы310-323
Число страниц14
ISBN (печатное издание)9783030108007
DOI
СостояниеОпубликовано - 1 янв 2019
Событие45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 - Nový Smokovec, Словакия
Продолжительность: 27 янв 201930 янв 2019

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том11376 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018
Страна/TерриторияСловакия
ГородNový Smokovec
Период27/01/1930/01/19

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 41137431