Abstract:
Somewhat recently, Bakinova et al. have introduced the family of GF(2)-grammars. As a whole, the family of GF(2)-grammars is notable for having many algebraic properties that the family of ordinary context-free grammars does not. In “Bounded languages described by GF(2)-grammars”, Makarov proved a necessary condition for the subsets of $a_1^* a_2^* \cdots a_k^*$ to be described by some GF(2)-grammar. By extending his methods further, we get a finer upper and lower bounds on the subsets of $a_1^* a_2^* \cdots a_n^*$ described by GF(2)-grammars. Said upper and lower bounds are expressed in terms of the families of noninterleaving subintervals of $\{1, 2, \ldots, n\}$.
Fulltext:
PDF file (532 kB)
First page:
PDF file