30 citations · 111 across the 34 of their papers we have counts for
6 papers · 1 filter
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…
Regular Boardgames
Jakub Kowalski, Maksymilian Mika, Jakub Sutowicz +1
We propose a new General Game Playing (GGP) language called Regular Boardgames (RBG), which is based on the theory of regular languages. The objective of RBG is to join key propert…
Preimage problems for deterministic finite automata
Mikhail V. Berlinkov, Robert Ferens, Marek Szykuła
Given a subset of states of a deterministic finite automaton and a word , the preimage is the subset of all states mapped to a state in by the action of . We study th…
Improving the upper bound on the length of the shortest reset words
Marek Szykuła
We improve the best known upper bound on the length of the shortest reset words of synchronizing automata. The new bound is slightly better than . The Černý…
Existential length universality
Paweł Gawrychowski, Martin Lange, Narad Rampersad +2
We study the following natural variation on the classical universality problem: given a language represented by (e.g., a DFA/RE/NFA/PDA), does there exist an integer $\e…
Complexity of regular bifix-free languages
Robert Ferens, Marek Szykuła
We study descriptive complexity properties of the class of regular bifix-free languages, which is the intersection of prefix-free and suffix-free regular languages. We show that th…