30 citations · 111 across the 34 of their papers we have counts for
5 papers · 1 filter
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…
Simplified Boardgames
Jakub Kowalski, Jakub Sutowicz, Marek Szykuła
We formalize Simplified Boardgames language, which describes a subclass of arbitrary board games. The language structure is based on the regular expressions, which makes the rules…
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…