23 citations · 53 across the 7 of their papers we have counts for
4 papers · 1 filter
Transition Complexity of Incomplete DFAs
Yuan Gao, Kai Salomaa, Sheng Yu
In this paper, we consider the transition complexity of regular languages based on the incomplete deterministic finite automata. A number of results on Boolean operations have been…
State Complexity of Catenation Combined with Star and Reversal
Bo Cui, Yuan Gao, Lila Kari +1
This paper is a continuation of our research work on state complexity of combined operations. Motivated by applications, we study the state complexities of two particular combined…
State Complexity of Two Combined Operations: Reversal-Catenation and Star-Catenation
Bo Cui, Yuan Gao, Lila Kari +1
In this paper, we show that, due to the structural properties of the resulting automaton obtained from a prior operation, the state complexity of a combined operation may not be eq…
State complexity of union and intersection combined with star and reversal
Yuan Gao, Sheng Yu
In this paper, we study the state complexities of union and intersection combined with star and reversal, respectively. We obtain the state complexities of these combined operation…