Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
type: Item
instance of: scholarly article
title: Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
zbMATH Open document ID: 1380.68257
author: Pavel Martyugin
published in: Theory of Computing Systems
publication date: 2017-11-07T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6803499
zbMATH Keywords: synchronization
zbMATH Keywords: automata
zbMATH Keywords: directing words
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
full work available at URL: s00224-013-9516-6
OpenAlex ID: W2140195055
cites work: Q4120536
cites work: Q5509690
cites work: Reset Sequences for Monotonic Automata
cites work: Improved upper bounds on synchronizing nondeterministic automata
cites work: Directable nondeterministic automata
cites work: Q4439451
cites work: Theory Is Forever
cites work: Algebraic Theory of Automata and Languages
cites work: Q3115697
cites work: A lower bound for the length of the shortest carefully synchronizing words
cites work: Complexity of Problems Concerning Carefully Synchronizing Words for PFA and Directing Words for NFA
cites work: Synchronization of Automata with One Undefined or Ambiguous Transition
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Modifying the Upper Bound on the Length of Minimal Synchronizing Word
cites work: Synchronizing Automata and the Černý Conjecture
DOI: 10.1007/S00224-013-9516-6
Recommended article: Complexity of Problems Concerning Carefully Synchronizing Words for PFA and Directing Words for NFA
Recommended article: On the Computational Complexity of Partial Word Automata Problems
Recommended article: Careful Synchronization of Partial Automata with Restricted Alphabets
Recommended article: Lower Bound for the Length of Synchronizing Words in Partially-Synchronizing Automata
Recommended article: Q5306174
Recommended article: Q5422229
Recommended article: Complexities of Some Problems Related to Synchronizing, Non-Synchronizing and Monotonic Automata
Recommended article: Synchronizing Automata over Nested Words
Recommended article: Lower Bounds for Synchronizing Word Lengths in Partial Automata
description: scientific article; zbMATH DE number 6803499