Verkauf durch Sack Fachmedien

Hoffmann

The Set of Synchronizing Words and the Constrained Synchronization Problem

Medium: Buch
ISBN: 978-3-032-44452-3
Verlag: Springer
Erscheinungstermin: 24.02.2027
vorbestellbar, Erscheinungstermin ca. Februar 2027

Finite automata process input sequences, called words, and model a wide variety of systems, e.g., sequential circuits, decoders in data transmission, or simple behavior patterns in artificial intelligence. In all these situations, knowing whether we can reset the system is of interest. An input sequence that resets an automaton, regardless of its current state, is called a synchronizing word.

This book treats two topics. The first is the set of synchronizing words of an automaton. This set forms a regular language, but the smallest automaton accepting it can be exponentially larger than the original one. The author shows that its size is determined by the reachability and distinguishability of subsets of states, characterizes the automata for which it is the largest possible, and obtains new characterizations of primitive permutation groups. The second topic is the constrained synchronization problem, where the synchronizing word must belong to a fixed regular language. The author investigates how the computational complexity of this problem, which ranges from Alternating Circuit Depth 0 to PSPACE-complete, depends on the constraint language and on the type of input automaton, and determines it completely for several classes of constraint languages.


Produkteigenschaften


  • Artikelnummer: 9783032444523
  • Medium: Buch
  • ISBN: 978-3-032-44452-3
  • Verlag: Springer
  • Erscheinungstermin: 24.02.2027
  • Sprache(n): Englisch
  • Auflage: Erscheinungsjahr 2027
  • Serie: Lecture Notes in Computer Science
  • Produktform: Kartoniert
  • Format (B x H): 155 x 235 mm
  • Ausgabetyp: Kein, Unbekannt
Autoren/Hrsg.

Autoren

Short Introduction to Synchronizing Automata.- Outline and Contribution.- General Notions.- Classes of Transformations.- Permutation Groups.- Notions From Automata Theory.- Classes of Automata.- Subset Mapping Problems.- Reachable Sets and Pairs of Distinguishable Sets.- Sync-Maximal Automata.- Graph-Theoretical Constructions.- Classes of Automata.- Decision Problems.- Permutation Groups.- Slowly Synchronizing Automata.- Motivational Examples.- Further Notions and Preliminaries.- General Results.- Classes of Contraint Languages.- Classes of Input Automata.