Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/118011
Title: Careful synchronization of partial deterministic finite automata
Authors: Shabana, H.
Volkov, M. V.
Issue Date: 2022
Publisher: Springer Science and Business Media Deutschland GmbH
Citation: Shabana H. Careful synchronization of partial deterministic finite automata / H. Shabana, M. V. Volkov // Acta Informatica. — 2022. — Vol. 59. — Iss. 4. — P. 479-504.
Abstract: We approach the task of computing a carefully synchronizing word of minimum length for a given partial deterministic automaton, encoding the problem as an instance of SAT and invoking a SAT solver. Our experiments demonstrate that this approach gives satisfactory results for automata with up to 100 states even if very modest computational resources are used. We compare our results with the ones obtained by the first author for exact synchronization, which is another version of synchronization studied in the literature, and draw some theoretical conclusions. © 2022, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.
Keywords: COMPUTATIONAL RESOURCES
DETERMINISTIC AUTOMATON
DETERMINISTIC FINITE AUTOMATA
ENCODINGS
SYNCHRONIZING WORDS
SYNCHRONIZATION
URI: http://hdl.handle.net/10995/118011
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 85134678836
ISSN: 15903
DOI: 10.1007/s00236-022-00433-1
metadata.dc.description.sponsorship: Ministry of Education and Science of the Russian Federation, Minobrnauka: FEUZ-2020-0016
Supported by the Ministry of Science and Higher Education of the Russian Federation, project FEUZ-2020-0016.
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-85134678836.pdf284,21 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.