The Library
Synchronizing automata over nested words
Tools
Chistikov, Dmitry, Martyugin, Pavel and Shirmohammadi, Mahsa (2016) Synchronizing automata over nested words. In: 19th International Conference, FOSSACS 2016, Eindhoven, The Netherlands, 2-8 Arp 2016. Published in: Foundations of Software Science and Computation Structures. FoSSaCS 2016, 9634 pp. 252-268. ISBN 9783662496299. doi:10.1007/978-3-662-49630-5_15 ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-662-49630-5_15
Abstract
We extend the concept of a synchronizing word from deterministic finite-state automata (DFA) to nested word automata (NWA): A well-matched nested word is called synchronizing if it resets the control state of any configuration, i.e., takes the NWA from all control states to a single control state.
We show that although the shortest synchronizing word for an NWA, if it exists, can be (at most) exponential in the size of the NWA, the existence of such a word can still be decided in polynomial time. As our main contribution, we show that deciding the existence of a short synchronizing word (of at most given length) becomes PSPACE-complete (as opposed to NP-complete for DFA). The upper bound makes a connection to pebble games and Strahler numbers, and the lower bound goes via small-cost synchronizing words for DFA, an intermediate problem that we also show PSPACE-complete. We also characterize the complexity of a number of related problems, using the observation that the intersection nonemptiness problem for NWA is EXP-complete.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Journal or Publication Title: | Foundations of Software Science and Computation Structures. FoSSaCS 2016 | ||||
Publisher: | Springer | ||||
ISBN: | 9783662496299 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Foundations of Software Science and Computation Structures | ||||
Official Date: | 2016 | ||||
Dates: |
|
||||
Volume: | 9634 | ||||
Page Range: | pp. 252-268 | ||||
DOI: | 10.1007/978-3-662-49630-5_15 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 19th International Conference, FOSSACS 2016 | ||||
Type of Event: | Conference | ||||
Location of Event: | Eindhoven, The Netherlands | ||||
Date(s) of Event: | 2-8 Arp 2016 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |