2022/06/10 by Pascal Caron, Caron, Pascal, Edwin Hamel-de-le court +3
Computer Science · #Advanced Algebra and Logic #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning and Algorithms #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2206.05100
openalex publication_date 2022/06/10 · openalex created_date 2022/06/14 · openalex updated_date 2026/07/28
Monsters and modifiers are two concepts recently developed in the state complexity theory. 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. The paper describes a general strategy that can be used to compute the state complexity of many operations. We illustrate it on the problem of the star of a Boolean operation. After applying modifiers on monsters, the states of the resulting automata are assimilated to combinatorial objects: the tableaux. We investigate the combinatorics of these tableaux in order to deduce the state complexity. Specifically, we recover the state complexity of star of intersection and star of union, and we also give the exact state complexity of star of symmetrical difference. We thus harmonize the search strategy for the state complexity of star of any Boolean operations.