Abstrakt. Vi studerar flera problem relaterade till att hitta återställ ord i deterministisk ändlig automata. Vi konstaterar särskilt att problemet med att avgöra om ett kortare återställningsord har längd k är komplett för komplexitetsklass DP. Detta resultat besvarar en fråga från Volkov. För sökproblemen med att hitta ett kortare återställningsord och längden på ett kortare återställningsord, etablerar vi medlemskap i komplexitetsklasserna FP NP respektive FP NP [log]. Dessutom visar vi att båda dessa problem är svåra för FP NP [log]. Slutligen observerar vi att beräkning av ett återställningsord av en viss längd är FNP-komplett.
Dessutom visade Olschewski och Ummels att hitta den minsta återställningssekvensen och bestämma längden på den minsta återställningssekvensen är i FP NP respektive FP NP [log] respektive REF.
The Complexity of Finding Reset Words in Finite Automata
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}