DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2022.14

The Synchronization Game on Subclasses of Automata

Authors: Henning Fernau, Carolina Haase, and Stefan Hoffmann

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract

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.

Cite as

Henning Fernau, Carolina Haase, and Stefan Hoffmann. The Synchronization Game on Subclasses of Automata. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fernau_et_al:LIPIcs.FUN.2022.14,
  author =	{Fernau, Henning and Haase, Carolina and Hoffmann, Stefan},
  title =	{{The Synchronization Game on Subclasses of Automata}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.14},
  URN =		{urn:nbn:de:0030-drops-159842},
  doi =		{10.4230/LIPIcs.FUN.2022.14},
  annote =	{Keywords: Synchronization of finite automata, computational complexity}
}

Search Results

Documents authored by Haase, Carolina

The Synchronization Game on Subclasses of Automata

Abstract

Cite as

Thanks for your feedback!

Could not send message