The Synchronization Game on Subclasses of Automata
| Autor: | Fernau, Henning, Haase, Carolina, Hoffmann, Stefan |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Synchronization of finite automata computational complexity Nonlinear Sciences::Cellular Automata and Lattice Gases Theory of computation → Regular languages Theory of computation → Complexity classes Computer Science::Formal Languages and Automata Theory |
| DOI: | 10.4230/lipics.fun.2022.14 |
| Popis: | The notion of synchronization of finite automata is connected to one of the long-standing open problems in combinatorial automata theory, which is Černý’s Conjecture. In this paper, we focus on so-called synchronization games. We will discuss how to present synchronization questions in a playful way. This leads us to study related complexity questions on certain classes of finite automata. More precisely, we consider weakly acyclic, commutative and k-simple idempotent automata. We encounter a number of complexity classes, ranging from L up to PSPACE. LIPIcs, Vol. 226, 11th International Conference on Fun with Algorithms (FUN 2022), pages 14:1-14:17 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|