Pascal Caron ; Edwin Hamel-De le court ; Jean-Gabriel Luque ; Bruno Patrou - New tools for state complexity

dmtcs:4835 - Discrete Mathematics & Theoretical Computer Science, March 16, 2020, vol. 22 no. 1 - https://doi.org/10.23638/DMTCS-22-1-9
New tools for state complexityArticle

Authors: Pascal Caron ORCID; Edwin Hamel-De le court ; Jean-Gabriel Luque ; Bruno Patrou

    A monster is an automaton in which every function from states to states is represented by at least one letter. A modifier is a set of functions allowing one to transform a set of automata into one automaton. We revisit some language transformation algorithms in terms of modifier and monster. These new theoretical concepts allow one to find easily some state complexities. We illustrate this by retrieving the state complexity of the Star of Intersection and the one of the Square root operation.

    https://doi.org/10.23638/DMTCS-22-1-9
    Source: arXiv.org:1807.00663
    Volume: vol. 22 no. 1
    Section: Automata, Logic and Semantics
    Published on: March 16, 2020
    Accepted on: February 12, 2020
    Submitted on: September 18, 2018
    Keywords: Computer Science - Formal Languages and Automata Theory
    Licence: arXiv.org - Non-exclusive license to distribute

    Classifications

    Mathematics Subject Classification 20201
    Sources:
    • [1] zbMATH Open.

    1 Document citing this article

    Share and export

    Consultation statistics

    This page has been seen 1039 times.
    This article's PDF has been downloaded 286 times.