Reset Complexity of Ideal Languages Over a Binary Alphabet

We prove PSPACE-completeness of checking whether a given ideal language serves as the language of reset words for some automaton with at most four states over a binary alphabet. We compare the reset complexity and the state complexity for languages related to slowly synchronizing automata.

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2019-09, Vol.30 (6n07), p.1177-1196
Main Author: Maslennikova, Marina
Format: Article
Language:English
Subjects:
Complexity
Languages
Synchronism
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We prove PSPACE-completeness of checking whether a given ideal language serves as the language of reset words for some automaton with at most four states over a binary alphabet. We compare the reset complexity and the state complexity for languages related to slowly synchronizing automata.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054119400343