30 citations · 111 across the 34 of their papers we have counts for
6 papers · 1 filter
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…
Generating Synchronizing Automata with Large Reset Lengths
Andrzej Kisielewicz, Marek Szykuła
We study synchronizing automata with the shortest reset words of relatively large length. First, we refine the Frankl-Pin result on the length of the shortest words of rank , an…
Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals
Janusz Brzozowski, Marek Szykuła
We solve two open problems concerning syntactic complexity: We prove that the cardinality of the syntactic semigroup of a left ideal or a suffix-closed language with left quoti…
Large Aperiodic Semigroups
Janusz Brzozowski, Marek Szykuła
The syntactic complexity of a regular language is the size of its syntactic semigroup. This semigroup is isomorphic to the transition semigroup of the minimal deterministic finite…