Synchronizing words under \textsf{LTL} constraints

DOI10.1016/J.IPL.2023.106392MaRDI QIDQ6161453zbMATH OpenOpenAlexFDO

Authors Nathalie Bertrand, Hugo Francon, Nicolas Markey

Publication date 5 June 2023

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2023.106392

zbMATH Keywords

finite-state automataformal methodssynchronizing wordstemporal logic

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Synchronizing words for weighted and timed automata
• Semicomputable points in Euclidean spaces
• Recognizing synchronizing automata with finitely many minimal synchronizing words is PSPACE-complete
• Constrained synchronization and subset synchronization problems for weakly acyclic automata
• Synchronization of automata with one undefined or ambiguous transition

Cites work

• An extremal problem for two families of sets
• An improvement to a recent upper bound for synchronizing words of finite automata
• scientific article; zbMATH DE number 7228447 (Why is no real title available?)
• scientific article; zbMATH DE number 5585443 (Why is no real title available?)
• scientific article; zbMATH DE number 3222112 (Why is no real title available?)
• Infinite Synchronizing Words for Probabilistic Automata
• On the Length of the Smallest Uniform Experiment which Distinguishes the Terminal States of a Machine
• On two Combinatorial Problems Arising from Automata Theory
• Polynomial complete problems in automata theory
• Relationships between nondeterministic and deterministic tape complexities
• Synchronizing Automata and the Černý Conjecture
• Synchronizing data words for register automata
• Synchronizing words for weighted and timed automata
• The Cerny Conjecture Holds with High Probability
• The complexity of propositional linear temporal logics
• The complexity of synchronizing Markov decision processes

Cited in

(2)

• scientific article; zbMATH DE number 7376069 (Why is no real title available?)
• The complexity of traversing automata with current state uncertainty under \(\mathrm{LTL}_{f}\) constraints

This page was built for publication: Synchronizing words under \textsf{LTL} constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6161453)