Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/101464
Title: Preimage problems for deterministic finite automata
Authors: Berlinkov, M. V.
Ferens, R.
Szykuła, M.
Issue Date: 2021
Publisher: Academic Press Inc.
Citation: Berlinkov M. V. Preimage problems for deterministic finite automata / M. V. Berlinkov, R. Ferens, M. Szykuła. — DOI 10.1016/j.jcss.2020.08.002 // Journal of Computer and System Sciences. — 2021. — Vol. 115. — P. 214-234.
Abstract: Given a subset of states S of a deterministic finite automaton and a word w, the preimage is the subset of all states mapped to a state in S by the action of w. We study three natural problems concerning words giving certain preimages. The first problem is whether, for a given subset, there exists a word extending the subset (giving a larger preimage). The second problem is whether there exists a totally extending word (giving the whole set of states as a preimage)—equivalently, whether there exists an avoiding word for the complementary subset. The third problem is whether there exists a resizing word. We also consider variants where the length of the word is upper bounded, where the size of the given subset is restricted, and where the automaton is strongly connected, synchronizing, or binary. We conclude with a summary of the complexities in all combinations of the cases. © 2020 Elsevier Inc.
Keywords: AVOIDING WORD
EXTENDING WORD
EXTENSIBLE SUBSET
RESET WORD
SYNCHRONIZING AUTOMATON
FINITE AUTOMATA
ROBOTS
DETERMINISTIC FINITE AUTOMATA
PRE IMAGES
PRE-IMAGE PROBLEM
STRONGLY CONNECTED
SET THEORY
URI: http://hdl.handle.net/10995/101464
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 85090002869
PURE ID: 13654241
b8eaa0c0-ad57-458b-ba05-33b905ce1edd
ISSN: 220000
DOI: 10.1016/j.jcss.2020.08.002
metadata.dc.description.sponsorship: We thank the anonymous referee for careful reading and detailed comments. This work was supported by the Competitiveness Enhancement Program of Ural Federal University under grant No. 02.A03.21.006 (Mikhail Berlinkov), and by the National Science Centre , Poland under project number 2014/15/B/ST6/00615 (Robert Ferens) and 2017/25/B/ST6/01920 (Marek Szykuła).
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-85090002869.pdf737,63 kBAdobe PDFView/Open


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