Alphabet-based synchronisation is exponentially cheaper

DOI10.1007/3-540-45694-5_12MaRDI QIDQ4484486zbMATH OpenFDO

Authors Antti Valmari, Antti Kervinen

Publication date 12 June 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2421/24210161.htm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Synchronization strings: highly efficient deterministic constructions over small alphabets
• Alphabetic coding with exponential costs
• Slowly synchronizing automata with fixed alphabet size
• Maximum performance at minimum cost in network synchronization
• On codeword lengths guaranteeing synchronization
• Synchronizing without locks is inherently expensive
• Efficient algorithms with asymmetric read and write costs
• The cost of synchronizing multiple-access channels
• On synchronizing prefix codes

Cited in

(4)

• Hardness of equivalence checking for composed finite-state systems
• A parametric analysis of the state-explosion problem in model checking
• Hardness of preorder checking for basic formalisms
• EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system

This page was built for publication: Alphabet-based synchronisation is exponentially cheaper

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