19 citations · 27 across the 3 of their papers we have counts for
3 papers
cs.FL2015★ 19 cited
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}-…
cs.FL2015★ 6 cited
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…
cs.FL2010★ 2 cited
Quotient Complexity of Star-Free Languages
Janusz Brzozowski, Bo Liu
The quotient complexity, also known as state complexity, of a regular language is the number of distinct left quotients of the language. The quotient complexity of an operation is…