19 citations · 121 across the 33 of their papers we have counts for
Showing 2018 · cs.FLShow all
3 papers · 2 filters
cs.FL2018
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…
cs.FL2018
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…
cs.FL2018
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…