23 citations · 53 across the 7 of their papers we have counts for
7 papers
A Survey on Operational State Complexity
Yuan Gao, Nelma Moreira, Rogério Reis +1
Descriptional complexity is the study of the conciseness of the various models representing formal languages. The state complexity of a regular language is the size, measured by th…
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…
State Complexity Approximation
Yuan Gao, Sheng Yu
In this paper, we introduce the new concept of state complexity approximation, which is a further development of state complexity estimation. We show that this new concept is usefu…