Complexities of some problems related to synchronizing, non-synchronizing and monotonic automata

Türker, Uraz Cengiz and Yenigün, Hüsnü (2015) Complexities of some problems related to synchronizing, non-synchronizing and monotonic automata. International Journal of Foundations of Computer Science, 26 (1). pp. 99-121. ISSN 0129-0541 (Print) 1793-6373 (Online)

This is the latest version of this item.

Full text not available from this repository. (Request a copy)

Abstract

In this study, we first introduce several problems related to finding reset words for deterministic finite automata, and present motivations for these problems for practical applications in areas such as robotics and bio-engineering. We then analyse computational complexities of these problems. Second, we consider monotonic and partially specified automata. Monotonicity is known to be a feature simplyfing the synchronizability problems. On the other hand for partially specified automata, synchronizability problems are known to be harder than the completely specified automata. We investigate the complexity of some synchronizability problems for automata that are both monotonic and partially specified. We show that checking the existence, computing one, and computing a shortest reset word for a monotonic partially specified automaton is NP-hard. We also show that finding a reset word that synchronizes $\mathcal{K}$ number of states (or maximum number of states) of a given monotonic non-synchronizable automaton to a given set of states is NP-hard.
Item Type: Article
Uncontrolled Keywords: Synchronizable automata; monotonic automata; reset words
Subjects: Q Science > QA Mathematics > QA076 Computer software
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Hüsnü Yenigün
Date Deposited: 18 Nov 2015 15:52
Last Modified: 23 Aug 2019 10:15
URI: https://research.sabanciuniv.edu/id/eprint/27257

Available Versions of this Item

Actions (login required)

View Item
View Item