30 citations · 111 across the 34 of their papers we have counts for
30 papers · 1 filter
Synchronizing Automata: Open Problems
Marek Szykuła
We survey selected open problems in the theory of synchronizing automata, centered around the famous ÄŒerný conjecture. A deterministic finite automaton is called synchronizing if…
Reset thresholds of transformation monoids
Igor Rystsov, Marek Szykuła
Motivated by the Černý conjecture for automata, we introduce the concept of monoidal automata, which allows the formulation of the Černý conjecture for monoids. We show upper bound…
Primitive Automata that are Synchronizing
Igor Rystsov, Marek Szykuła
A deterministic finite (semi)automaton is primitive if its transition monoid (semigroup) acting on the set of states has no non-trivial congruences. It is synchronizing if it conta…
Completely reachable automata: a quadratic decision algorithm and a quadratic upper bound on the reaching threshold
Robert Ferens, Marek Szykuła
A complete deterministic finite (semi)automaton (DFA) with a set of states is \emph{completely reachable} if every nonempty subset of is the image of the action of some wor…
An Improved Algorithm for Finding the Shortest Synchronizing Words
Marek Szykuła, Adam Zyzik
A synchronizing word of a deterministic finite complete automaton is a word whose action maps every state to a single one. Finding a shortest or a short synchronizing word is a cen…
Synchronization of strongly connected partial DFAs and prefix codes
Mikhail V. Berlinkov, Robert Ferens, Andrew Ryzhikov +1
We study synchronizing partial DFAs, which extend the classical concept of synchronizing complete DFAs and are a special case of synchronizing unambiguous NFAs. A partial DFA is ca…
The Frobenius and factor universality problems of the Kleene star of a finite set of words
Maksymilian Mika, Marek Szykuła
We solve open problems concerning the Kleene star of a finite set of words over an alphabet . The \emph{Frobenius monoid} problem is the question for a given finite se…
Finding Short Synchronizing Words for Prefix Codes
Andrew Ryzhikov, Marek Szykuła
We study the problems of finding a shortest synchronizing word and its length for a given prefix code. This is done in two different settings: when the code is defined by an arbitr…
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…
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…
Synchronizing Automata with Extremal Properties
Andrzej Kisielewicz, Marek Szykuła
We present a few classes of synchronizing automata exhibiting certain extremal properties with regard to synchronization. The first is a series of automata with subsets whose short…
Experiments with Synchronizing Automata
Andrzej Kisielewicz, Jakub Kowalski, Marek Szykuła
We have improved an algorithm generating synchronizing automata with a large length of the shortest reset words. This has been done by refining some known results concerning bounds…
Syntactic complexity of bifix-free languages
Marek Szykuła, John Wittnebel
We study the properties of syntactic monoids of bifix-free regular languages. In particular, we solve an open problem concerning syntactic complexity: We prove that the cardinality…
An Extremal Series of Eulerian Synchronizing Automata
Marek Szykuła, Vojtěch Vorel
We present an infinite series of -state Eulerian automata whose reset words have length at least . This improves the current lower bound on the length of shortest res…
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…
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…
Algebraic synchronization criterion and computing reset words
Mikhail Berlinkov, Marek Szykuła
We refine a uniform algebraic approach for deriving upper bounds on reset thresholds of synchronizing automata. We express the condition that an automaton is synchronizing in terms…
Syntactic Complexity of Suffix-Free Languages
Janusz Brzozowski, Marek Szykuła
We solve an open problem concerning syntactic complexity: We prove that the cardinality of the syntactic semigroup of a suffix-free language with left quotients (that is, with…
Checking Whether an Automaton Is Monotonic Is NP-complete
Marek Szykuła
An automaton is monotonic if its states can be arranged in a linear order that is preserved by the action of every letter. We prove that the problem of deciding whether a given aut…