3 citations · 8 across the 6 of their papers we have counts for
5 papers · 1 filter
A combinatorial approach for the state complexity of the Shuffle product
Pascal Caron, Jean-Gabriel Luque, Bruno Patrou
We investigate the state complexity of the shuffle operation on regular languages initiated by Campeanu et al. and studied subsequently by Brzozowski et al. We shift the problem in…
New tools for state complexity
Pascal Caron, Edwin Hamel-De le court, Jean-Gabriel Luque +1
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 a…
State complexity of catenation combined with boolean operations
Pascal Caron, Jean-Gabriel Luque, Bruno Patrou
We exhaustively investigate possible combinations of a boolean operation together with a catenation. In many cases we prove and improve some conjectures by Brzozowski. For each fam…
State complexity of multiple catenation
Pascal Caron, Jean-Gabriel Luque, Bruno Patrou
We improve some results relative to the state complexity of the multiple catenation described by Gao and Yu. In particular we nearly divide by 2 the size of the alphabet needed for…
State complexity of catenation combined with a boolean operation: a unified approach
Pascal Caron, Jean-Gabriel Luque, Ludovic Mignot +1
In this paper we study the state complexity of catenation combined with symmetric difference. First, an upper bound is computed using some combinatoric tools. Then, this bound is s…