19 citations · 121 across the 33 of their papers we have counts for
4 papers · 2 filters
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…
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…
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…
Quotient Complexities of Atoms of Regular Languages
Janusz Brzozowski, Hellis Tamm
An atom of a regular language L with n (left) quotients is a non-empty intersection of uncomplemented or complemented quotients of L, where each of the n quotients appears in a ter…