E-resources
Peer reviewed
-
Okhotin, Alexander; Radionova, Maria; Sazhneva, Elizaveta
Theoretical computer science, 05/2024, Volume: 995Journal Article
GF(2)-operations on formal languages (Bakinova et al., “Formal languages over GF(2)”, Inf. Comput., 2022) are variants of the classical concatenation and Kleene star obtained by replacing Boolean logic in their definitions with the GF(2) field. This paper investigates closure and non-closure of basic families of languages under these operations. First, it is proved that the group languages (those defined by permutation automata) are closed under GF(2)-concatenation and not closed under GF(2)-star; furthermore, the state complexity of GF(2)-concatenation for m-state and n-state permutation automata is determined as m⋅2n. Next, it is shown that the languages defined by trellis automata (one-way real-time cellular automata) are not closed under either operation, but are closed under GF(2)-concatenation with regular languages; the context-free languages and their linear and unambiguous variants are not closed under GF(2)-concatenation with a two-element set, nor under GF(2)-star; the LR(k) languages are closed under GF(2)-concatenation with a regular set on the right, but not on the left. •Two operations on formal languages, GF(2)-concatenation and GF(2)-star, are investigated.•The language family recognized by permutation automata is closed under GF(2)-concatenation, but not under GF(2)-star.•The language families defined by context-free grammars and their main subclasses are not closed under either operation.•The family recognized by trellis automata is closed under GF(2)-concatenation with regular sets.•The family defined by LR(k) grammars is closed under GF(2) concatenation with regular sets on the right, but not on the left.
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
If the library membership card is not in the list,
add a new one.
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|
Source: Personal bibliographies
and: SICRIS
The material is available in full text. If you wish to order the material anyway, click the Continue button.