Geodesic
Most Complex Regular Ideal Languages
Discrete mathematics & theoretical computer science, Tome 18 (2015-2016) no. 3.

Voir la notice de l'article provenant de la source Episciences

A right ideal (left ideal, two-sided ideal) is a non-empty language $L$ over an alphabet $\Sigma$ such that $L=L\Sigma^*$ ($L=\Sigma^*L$, $L=\Sigma^*L\Sigma^*$). Let $k=3$ for right ideals, 4 for left ideals and 5 for two-sided ideals. We show that there exist sequences ($L_n \mid n \ge k $) of right, left, and two-sided regular ideals, where $L_n$ has quotient complexity (state complexity) $n$, such that $L_n$ is most complex in its class under the following measures of complexity: the size of the syntactic semigroup, the quotient complexities of the left quotients of $L_n$, the number of atoms (intersections of complemented and uncomplemented left quotients), the quotient complexities of the atoms, and the quotient complexities of reversal, star, product (concatenation), and all binary boolean operations. In that sense, these ideals are "most complex" languages in their classes, or "universal witnesses" to the complexity of the various operations. 
@article{DMTCS_2016_18_3_a13,
     author = {Brzozowski, Janusz and Davies, Sylvie and Liu, Bo Yang Victor},
     title = {Most {Complex} {Regular} {Ideal} {Languages}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {18},
     number = {3},
     year = {2015-2016},
     doi = {10.46298/dmtcs.1343},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.1343/}
}
TY  - JOUR
AU  - Brzozowski, Janusz
AU  - Davies, Sylvie
AU  - Liu, Bo Yang Victor
TI  - Most Complex Regular Ideal Languages
JO  - Discrete mathematics & theoretical computer science
PY  - 2015-2016
VL  - 18
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.1343/
DO  - 10.46298/dmtcs.1343
LA  - en
ID  - DMTCS_2016_18_3_a13
ER  - 
%0 Journal Article
%A Brzozowski, Janusz
%A Davies, Sylvie
%A Liu, Bo Yang Victor
%T Most Complex Regular Ideal Languages
%J Discrete mathematics & theoretical computer science
%D 2015-2016
%V 18
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.1343/
%R 10.46298/dmtcs.1343
%G en
%F DMTCS_2016_18_3_a13
Brzozowski, Janusz; Davies, Sylvie; Liu, Bo Yang Victor. Most Complex Regular Ideal Languages. Discrete mathematics & theoretical computer science, Tome 18 (2015-2016) no. 3. doi : 10.46298/dmtcs.1343. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.1343/

Cité par Sources :