E-resources
Peer reviewed
-
Okhotin, Alexander; Sazhneva, Elizaveta
Information and computation, March 2022, 2022-03-00, Volume: 284Journal Article
The paper investigates the state complexity of two operations on regular languages, known as GF(2)-concatenation and GF(2)-inverse (Bakinova et al., “Formal languages over GF(2)”, LATA 2018), in the case of a one-symbol alphabet. The GF(2)-concatenation is a variant of the classical concatenation obtained by replacing Boolean logic in its definition with the GF(2) field; it is proved that GF(2)-concatenation of two unary languages recognized by an m-state and an n-state DFA is recognized by a DFA with 2mn states, and this number of states is necessary in the worst case, as long as m and n are relatively prime. This operation is known to have an inverse, and the state complexity of the GF(2)-inverse operation over a unary alphabet is proved to be exactly 2n−1+1, with the proof based on primitive polynomials over GF(2). For a generalization of the GF(2)-inverse, called the GF(2)-star, the state complexity in the unary case is exactly 2n.
![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.