30 citations · 111 across the 34 of their papers we have counts for
5 papers · 1 filter
On the State Complexity of the Shuffle of Regular Languages
Janusz Brzozowski, Galina Jirásková, Bo Liu +2
We investigate the shuffle operation on regular languages represented by complete deterministic finite automata. We prove that $f(m,n)=2^{mn-1} + 2^{(m-1)(n-1)}(2^{m-1}-1)(2^{n-1}-…
Syntactic complexity of regular ideals
Janusz A. Brzozowski, Marek Szykuła, Yuli Ye
The state complexity of a regular language is the number of states in a minimal deterministic finite automaton accepting the language. The syntactic complexity of a regular languag…
On the Number of Synchronizing Colorings of Digraphs
Vladimir V. Gusev, Marek Szykuła
We deal with -out-regular directed multigraphs with loops (called simply \emph{digraphs}). The edges of such a digraph can be colored by elements of some fixed -element set i…
Procedural Content Generation for GDL Descriptions of Simplified Boardgames
Jakub Kowalski, Marek Szykuła
We present initial research towards procedural generation of Simplified Boardgames and translating them into an efficient GDL code. This is a step towards establishing Simplified B…
Complexity of Suffix-Free Regular Languages
Janusz Brzozowski, Marek Szykuła
We study various complexity properties of suffix-free regular languages. The quotient complexity of a regular language is the number of left quotients of ; this is the same…