30 citations · 111 across the 34 of their papers we have counts for
41 papers
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…
Regular Games -- an Automata-Based General Game Playing Language
Radosław Miernik, Marek Szykuła, Jakub Kowalski +3
We propose a new General Game Playing (GGP) system called Regular Games (RG). The main goal of RG is to be both computationally efficient and convenient for game design. The system…
Fast and Knowledge-Free Deep Learning for General Game Playing (Student Abstract)
Michał Maras, Michał Kępa, Jakub Kowalski +1
We develop a method of adapting the AlphaZero model to General Game Playing (GGP) that focuses on faster model generation and requires less knowledge to be extracted from the game…
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…
Split Moves for Monte-Carlo Tree Search
Jakub Kowalski, Maksymilian Mika, Wojciech Pawlik +3
In many games, moves consist of several decisions made by the player. These decisions can be viewed as separate moves, which is already a common practice in multi-action games for…
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…
Efficient Reasoning in Regular Boardgames
Jakub Kowalski, Radosław Miernik, Maksymilian Mika +4
We present the technical side of reasoning in Regular Boardgames (RBG) language -- a universal General Game Playing (GGP) formalism for the class of finite deterministic games with…
Experimental Studies in General Game Playing: An Experience Report
Jakub Kowalski, Marek Szykuła
We describe nearly fifteen years of General Game Playing experimental research history in the context of reproducibility and fairness of comparisons between various GGP agents and…
A note on the empirical comparison of RBG and Ludii
Jakub Kowalski, Maksymilian Mika, Jakub Sutowicz +1
We present an experimental comparison of the efficiency of three General Game Playing systems in their current versions: Regular Boardgames (RBG 1.0), Ludii~0.3.0, and a Game Descr…
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…
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…
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…