6 citations · 14 across the 5 of their papers we have counts for
9 papers
A General Approach to State Complexity of Operations: Formalization and Limitations
Sylvie Davies
The state complexity of the result of a regular operation is often positively correlated with the number of distinct transformations induced by letters in the minimal deterministic…
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…
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…
A New Technique for Reachability of States in Concatenation Automata
Sylvie Davies
We present a new technique for demonstrating the reachability of states in deterministic finite automata representing the concatenation of two languages. Such demonstrations are a…
State Complexity of Reversals of Deterministic Finite Automata with Output
Sylvie Davies
We investigate the worst-case state complexity of reversals of deterministic finite automata with output (DFAOs). In these automata, each state is assigned some output value, rathe…
Primitivity, Uniform Minimality and State Complexity of Boolean Operations
Sylvie Davies
A minimal deterministic finite automaton (DFA) is uniformly minimal if it always remains minimal when the final state set is replaced by a non-empty proper subset of the state set.…
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…
Most Complex Regular Ideal Languages
Janusz Brzozowski, Sylvie Davies, Bo Yang Victor Liu
A right ideal (left ideal, two-sided ideal) is a non-empty language over an alphabet such that (, ). Let for right ideals, 4 for left idea…
Quotient Complexities of Atoms in Regular Ideal Languages
Janusz Brzozowski, Sylvie Davies
A (left) quotient of a language by a word is the language . The quotient complexity of a regular language is the number of quotients of ;…