Computational complexity of synchronization under regular commutative constraints

DOI10.1007/978-3-030-58150-3_37OpenAlexW3105271807MaRDI QIDQ2019491

Stefan Hoffmann

Publication date: 21 April 2021

Full work available at URL: https://arxiv.org/abs/2005.04042

zbMATH Keywords

computational complexityautomata theoryconstrained synchronizationcommutative language

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Related Items (4)

Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Computational complexity of synchronization under sparse regular constraints ⋮ Ideal separation and general theorems for constrained synchronization and their application to small constraint automata ⋮ Constrained synchronization and commutativity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Commutative regular languages -- properties and state complexity
• Synchronizing Automata of Bounded Rank
• Synchronization of Automata with One Undefined or Ambiguous Transition
• Learning Commutative Regular Languages
• Synchronizing Automata and the Černý Conjecture
• Semicomputable points in Euclidean spaces

This page was built for publication: Computational complexity of synchronization under regular commutative constraints