11 citations · 19 across the 4 of their papers we have counts for
Showing 2012 · cs.FLShow all
3 papers · 2 filters
cs.FL2012
Universal Witnesses for State Complexity of Boolean Operations and Concatenation Combined with Star
Janusz Brzozowski, David Liu
We study the state complexity of boolean operations and product (concatenation, catenation) combined with star. We derive tight upper bounds for the symmetric differences and diffe…
cs.FL2012★ 4 cited
Universal Witnesses for State Complexity of Basic Operations Combined with Reversal
Janusz Brzozowski, David Liu
We study the state complexity of boolean operations, concatenation and star with one or two of the argument languages reversed. We derive tight upper bounds for the symmetric diffe…
cs.FL2012★ 4 cited
Syntactic Complexity of Finite/Cofinite, Definite, and Reverse Definite Languages
Janusz Brzozowski, David Liu
We study the syntactic complexity of finite/cofinite, definite and reverse definite languages. The syntactic complexity of a class of languages is defined as the maximal size of sy…