19 citations · 121 across the 33 of their papers we have counts for
5 papers · 1 filter
Most Complex Regular Right-Ideal Languages
Janusz Brzozowski, Gareth Davies
A right ideal is a language L over an alphabet A that satisfies L = LA*. We show that there exists a stream (sequence) (R_n : n \ge 3) of regular right ideal languages, where R_n h…
Symmetric Groups and Quotient Complexity of Boolean Operations
Jason Bell, Janusz Brzozowski, Nelma Moreira +1
The quotient complexity of a regular language L is the number of left quotients of L, which is the same as the state complexity of L. Suppose that L and L' are binary regular langu…
Maximally Atomic Languages
Janusz Brzozowski, Gareth Davies
The atoms of a regular language are non-empty intersections of complemented and uncomplemented quotients of the language. Tight upper bounds on the number of atoms of a language an…
Maximal Syntactic Complexity of Regular Languages Implies Maximal Quotient Complexities of Atoms
Janusz Brzozowski, Gareth Davies
We relate two measures of complexity of regular languages. The first is syntactic complexity, that is, the cardinality of the syntactic semigroup of the language. That semigroup is…
Minimal Nondeterministic Finite Automata and Atoms of Regular Languages
Janusz Brzozowski, Hellis Tamm
We examine the NFA minimization problem in terms of atomic NFA's, that is, NFA's in which the right language of every state is a union of atoms, where the atoms of a regular langua…