Computational complexity of synchronization under sparse regular constraints

DOI10.1007/978-3-030-86593-1_19OpenAlexW3203280151MaRDI QIDQ2140506

Stefan Hoffmann

Publication date: 20 May 2022

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

zbMATH Keywords

computational complexityautomata theorybounded languagesconstrained synchronizationsparse languagesstrongly self-synchronizing codes

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Uses Software

• UMDES
• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Orienting polygonal parts without sensors
• The road coloring problem
• Synchronizing automata preserving a chain of partial orders
• Shortest path under rational constraint
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• On the regularity of languages generated by context-free evolutionary grammars
• Reset words for commutative and solvable automata
• Supervisory control of discrete-event systems
• The complexity of oblivious plans for orienting and distinguishing polygonal parts
• Computational complexity of synchronization under regular commutative constraints
• Complexity of road coloring with prescribed reset words
• The existential theory of equations with rational constraints in free groups is PSPACE-complete
• Synchronizing Automata of Bounded Rank
• Full Rank Factorization of Matrices
• Comma-Free Codes
• Introduction to Discrete Event Systems
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME
• Supervisory Control of a Class of Discrete Event Processes
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Observations about bounded languages and developmental systems
• Semicomputable points in Euclidean spaces
• Bounded Algol-Like Languages
• Bounded Regular Sets
• Similarity of automorphisms of the torus
• Principles and Practice of Constraint Programming – CP 2004

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