19 citations · 121 across the 33 of their papers we have counts for
40 papers
State Complexity of Pattern Matching in Regular Languages
Janusz A. Brzozowski, Sylvie Davies, Abhishek Madan
In a simple pattern matching problem one has a pattern and a text , which are words over a finite alphabet . One may ask whether occurs in , and if so, where? More…
Complexity of Proper Suffix-Convex Regular Languages
Corwin Sinnamon
A language L is suffix-convex if for any words u, v,w, whenever w and uvw are in L, vw is in L as well. Suffix-convex languages include left ideals, suffix-closed languages, and su…
Most Complex Deterministic Union-Free Regular Languages
Janusz A. Brzozowski, Sylvie Davies
A regular language is union-free if it can be represented by a regular expression without the union operation. A union-free language is deterministic if it can be accepted by a…
State Complexity of Overlap Assembly
Janusz Brzozowski, Lila Kari, Bai Li +1
The \emph{state complexity} of a regular language is the number of states in a minimal deterministic finite automaton (DFA) accepting . The state complexity of a reg…
Towards a Theory of Complexity of Regular Languages
Janusz A. Brzozowski
We survey recent results concerning the complexity of regular languages represented by their minimal deterministic finite automata. In addition to the quotient complexity of the la…
Most Complex Non-Returning Regular Languages
Janusz A. Brzozowski, Sylvie Davies
A regular language is non-returning if in the minimal deterministic finite automaton accepting it there are no transitions into the initial state. Eom, Han and Jirásková derive…