19 citations · 121 across the 33 of their papers we have counts for
5 papers · 2 filters
On the State Complexity of the Shuffle of Regular Languages
Janusz Brzozowski, Galina Jirásková, Bo Liu +2
We investigate the shuffle operation on regular languages represented by complete deterministic finite automata. We prove that $f(m,n)=2^{mn-1} + 2^{(m-1)(n-1)}(2^{m-1}-1)(2^{n-1}-…
Most Complex Regular Ideal Languages
Janusz Brzozowski, Sylvie Davies, Bo Yang Victor Liu
A right ideal (left ideal, two-sided ideal) is a non-empty language over an alphabet such that (, ). Let for right ideals, 4 for left idea…
Syntactic complexity of regular ideals
Janusz A. Brzozowski, Marek Szykuła, Yuli Ye
The state complexity of a regular language is the number of states in a minimal deterministic finite automaton accepting the language. The syntactic complexity of a regular languag…
Complexity of Suffix-Free Regular Languages
Janusz Brzozowski, Marek Szykuła
We study various complexity properties of suffix-free regular languages. The quotient complexity of a regular language is the number of left quotients of ; this is the same…
Quotient Complexities of Atoms in Regular Ideal Languages
Janusz Brzozowski, Sylvie Davies
A (left) quotient of a language by a word is the language . The quotient complexity of a regular language is the number of quotients of ;…