Buch, Englisch, Format (B × H): 155 mm x 235 mm
Reihe: Lecture Notes in Computer Science
ISBN: 978-3-032-44452-3
Verlag: Springer
Finite automata process input sequences, words, and they can be used to model a wide variety of systems, e.g., switching circuits, networks, or simple behavior patterns in artificial intelligence. In all these situations, knowing whether we can reset the system is of interest. This problem is tractable for completely specified and deterministic automata, but a small deviation from this optimal situation, e.g., having only partial information, allowing nondeterminism, or constraining the admissible input sequences, results in intractable algorithmic problems.
In this book the author is concerned with the constrained synchronization problem. In this setting, what computational complexity can we deduce from the kind of constraint put on the input sequences and/or types of input automata? The author states various results on how to manipulate sets of admissible synchronizing input sequences so as to retain a certain complexity of the problem, he identifies various conditions that either yield tractable or intractable problems, he investigates the classes of admissible sets of synchronizing sequences, and he considers different types of input automata to the problem.
Zielgruppe
Research
Autoren/Hrsg.
Weitere Infos & Material
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.
