Multi-buffer simulations: decidability and complexity

DOI10.1016/j.ic.2018.09.008zbMath1400.68105OpenAlexW2891953455MaRDI QIDQ1784963

Norbert Hundeshagen, Dietrich Kuske, Milka Hutagalung, 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

Büchi automataMazurkiewicz tracessimulation games

Mathematics Subject Classification ID

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

Cites Work

• Simulation relations for alternating Büchi automata
• Domino-tiling games
• Fair simulation
• Advanced automata minimization
• 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 ω-LANGUAGE
• Computing Simulations over Tree Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item