Authors: Janusz Brzozowski ; Sylvie Davies ; Bo Yang Victor Liu
NULL##NULL##NULL
Janusz Brzozowski;Sylvie Davies;Bo Yang Victor Liu
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.
Brzozowski, Janusz; SzykuĹa, Marek, 0000-0001-5349-468, 2015, Complexity Of Suffix-Free Regular Languages, Fundamentals Of Computation Theory, pp. 146-159, 10.1007/978-3-319-22177-9_12.
Brzozowski, Janusz A.; Davies, Sylvie, 2018, Most Complex Deterministic Union-Free Regular Languages, Descriptional Complexity Of Formal Systems, pp. 37-48, 10.1007/978-3-319-94631-3_4.
Davies, Sylvie, 2018, A New Technique For Reachability Of States In Concatenation Automata, Descriptional Complexity Of Formal Systems, pp. 75-87, 10.1007/978-3-319-94631-3_7.
Davies, Sylvie, 2018, Primitivity, Uniform Minimality, And State Complexity Of Boolean Operations, Mathematical Systems Theory, 62, 8, pp. 1952-2005, 10.1007/s00224-018-9859-0.
Ferens, Robert; SzykuĹa, Marek, 0000-0001-5349-468, 2019, Complexity Of Bifix-Free Regular Languages, Theoretical Computer Science, 787, pp. 14-27, 10.1016/j.tcs.2018.09.016.