Multi-buffer simulations: decidability and complexity

DOI10.1016/J.IC.2018.09.008zbMATH Open1400.68105OpenAlexW2891953455WikidataQ129327138 ScholiaQ129327138MaRDI QIDQ1784963FDOQ1784963

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

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)

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Domino-tiling games
• Computing Simulations over Tree Automata
• Fair simulation
• Simulation relations for alternating Büchi automata
• Title not available (Why is that?)
• Advanced automata minimization
• Title not available (Why is that?)
• Degrees of lookahead in regular infinite games
• Revealing vs. concealing: more simulation games for Büchi inclusion
• Three applications to rational relations of the high undecidability of the infinite Post correspondence problem in a regular \(\omega\)-language
• Buffered simulation games for Büchi automata
• Multi-buffer simulations for trace language inclusion

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
• Backwards-reachability for cooperating multi-pushdown systems
• Topological characterisation of multi-buffer simulation
• 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)