Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Issue title: The Fourth RuFiDiM Conference, Russian-Finnish Symposium in Discrete Mathematics
Guest editors: Vesa Halava, Juhani Karhumäki, Yuri Matiyasevich and Mikhail Volkov
Article type: Research Article
Authors: Ryzhikov, Andrewa; * | Shemyakov, Antonb
Affiliations: [a] LIGM, Université Paris-Est, 77455 Marne-la-Vallée, France; Laboratoire G-SCOP, Université Grenoble Alpes, 38031 Grenoble, France; United Institute of Informatics Problems of NASB, 220012 Minsk, Belarus, ryzhikov.andrew@gmail.com | [b] Belarusian State University, 220030 Minsk, Belarus
Correspondence: [*] Address for correspondence: LIGM, Université Paris-Est, 77455 Marne-la-Vallée, France
Abstract: We study extremal and algorithmic questions of subset and careful synchronization in monotonic automata. We show that several synchronization problems that are hard in general automata can be solved in polynomial time in monotonic automata, even without knowing a linear order of the states preserved by the transitions. We provide asymptotically tight bounds on the maximum length of a shortest word synchronizing a subset of states in a monotonic automaton and a shortest word carefully synchronizing a partial monotonic automaton. We provide a complexity framework for dealing with problems for monotonic weakly acyclic automata over a three-letter alphabet, and use it to prove NP-completeness and inapproximability of problems such as FINITE AUTOMATA INTERSECTION and the problem of computing the rank of a subset of states in this class. We also show that checking whether a monotonic partial automaton over a four-letter alphabet is carefully synchronizing is NP-hard. Finally, we give a simple necessary and sufficient condition when a strongly connected digraph with a selected subset of vertices can be transformed into a deterministic automaton where the corresponding subset of states is synchronizing.
Keywords: Synchronizing automaton, subset synchronization, careful synchronization, monotonic automaton
DOI: 10.3233/FI-2018-1721
Journal: Fundamenta Informaticae, vol. 162, no. 2-3, pp. 205-221, 2018
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
如果您在出版方面需要帮助或有任何建, 件至: editorial@iospress.nl