Algebraic and Combinatorial Tools for State Complexity : Application to the Star-Xor Problem

Pascal Caron
(LITIS, Université de Rouen)
Edwin Hamel-de le Court
(LITIS, Université de Rouen)
Jean-Gabriel Luque
(LITIS, Université de Rouen)

We investigate the state complexity of the star of symmetrical differences using modifiers and monsters. 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. These recent theoretical concepts allow one to find easily the desired state complexity. We then exhibit a witness with a constant size alphabet.

In Jérôme Leroux and Jean-Francois Raskin: Proceedings Tenth International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2019), Bordeaux, France, 2-3rd September 2019, Electronic Proceedings in Theoretical Computer Science 305, pp. 154–168.
Published: 18th September 2019.

ArXived at: https://dx.doi.org/10.4204/EPTCS.305.11 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org