Janusz Brzozowski ; Sylvie Davies ; Bo Yang Victor Liu - Most Complex Regular Ideal Languages

dmtcs:1343 - Discrete Mathematics & Theoretical Computer Science, October 17, 2016, Vol. 18 no. 3 - https://doi.org/10.46298/dmtcs.1343
Most Complex Regular Ideal LanguagesArticle

Authors: 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.


    Volume: Vol. 18 no. 3
    Section: Automata, Logic and Semantics
    Published on: October 17, 2016
    Accepted on: October 11, 2016
    Submitted on: October 14, 2016
    Keywords: Computer Science - Formal Languages and Automata Theory
    Funding:
      Source : OpenAIRE Graph
    • Funder: Natural Sciences and Engineering Research Council of Canada

    5 Documents citing this article

    Consultation statistics

    This page has been seen 833 times.
    This article's PDF has been downloaded 454 times.