Multi-buffer simulations: decidability and complexity

DOI10.1016/J.IC.2018.09.008MaRDI QIDQ1784963zbMATH OpenOpenAlexWikidataFDO

Authors Milka Hutagalung, Norbert Hundeshagen, Dietrich Kuske, Martin Lange, Etienne Lozes

Publication date 27 September 2018

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2018.09.008

zbMATH Keywords

Mazurkiewicz tracessimulation gamesBüchi automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Multi-buffer simulations for trace language inclusion
• Buffered simulation games for Büchi automata
• Topological characterisation of multi-buffer simulation
• Revealing vs. concealing: more simulation games for Büchi inclusion
• Multipebble simulations for alternating automata (extended abstract)

Cites work

• scientific article; zbMATH DE number 1048047 (Why is no real title available?)
• scientific article; zbMATH DE number 1927559 (Why is no real title available?)
• scientific article; zbMATH DE number 1500523 (Why is no real title available?)
• scientific article; zbMATH DE number 1754630 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Advanced automata minimization
• Buffered simulation games for Büchi automata
• Computing Simulations over Tree Automata
• Degrees of lookahead in regular infinite games
• Domino-tiling games
• Fair simulation
• Multi-buffer simulations for trace language inclusion
• Revealing vs. concealing: more simulation games for Büchi inclusion
• Simulation relations for alternating Büchi automata
• Three applications to rational relations of the high undecidability of the infinite Post correspondence problem in a regular \(\omega\)-language

Cited in

(7)

• Revealing vs. concealing: more simulation games for Büchi inclusion
• Buffered simulation games for Büchi automata
• Multi-buffer simulations for trace language inclusion
• Topological characterisation of multi-buffer simulation
• Topological characterisation of multi-buffer simulation
• Backwards-reachability for cooperating multi-pushdown systems
• Forwards- and backwards-reachability for cooperating multi-pushdown systems

This page was built for publication: Multi-buffer simulations: decidability and complexity

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