Simulation relations for alternating Büchi automata
The authors adapt the technique for minimalization of the nondeterministic Büchi automata to alternating Büchi automata. Based on the same simple game the authors define three types of simulation relations (direct, delayed and fair) for alternating Büchi automata and show that all these simulations can be used for checking language containment. Two new quotients (minimax and semi-elective) are presented and it is shown that the quotients preserve the languages recognized. It is shown that the simulation relations defined by the authors are compatible with standard translation of alternating Büchi automata to nondeterministic Büchi automata, due to Miyano and Hayashi. At the end an efficient algorithm for computing the simulation relations is presented. This algorithm has a lower time complexity than other existing algorithms.
- Constructing Büchi automata from linear temporal logic using simulation relations for alternating Büchi automata
- Simulation Relations for Alternating Parity Automata and Parity Games
- Simulation algorithms for symbolic automata
- Multipebble simulations for alternating automata (extended abstract)
- scientific article; zbMATH DE number 1954381
- Congruence Relations for Büchi Automata
- scientific article; zbMATH DE number 56675
- Complementation of Büchi Automata Using Alternation
- Publication:3033341
- Bisimulation relations for weighted automata
- An attack on a recursive authentication protocol. A cautionary tale
- An attack on the Needham-Schroeder public-key authentication protocol
- Deciding the security of protocols with commuting public key encryption
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- scientific article; zbMATH DE number 1962758 (Why is no real title available?)
- scientific article; zbMATH DE number 2043528 (Why is no real title available?)
- scientific article; zbMATH DE number 1927582 (Why is no real title available?)
- scientific article; zbMATH DE number 1927583 (Why is no real title available?)
- scientific article; zbMATH DE number 1754628 (Why is no real title available?)
- scientific article; zbMATH DE number 1754629 (Why is no real title available?)
- scientific article; zbMATH DE number 1759624 (Why is no real title available?)
- scientific article; zbMATH DE number 1903362 (Why is no real title available?)
- On the security of public key protocols
- Using encryption for authentication in large networks of computers
- Multi-buffer simulations: decidability and complexity
- Mediating for reduction (on minimizing alternating Büchi automata)
- Büchi automata can have smaller quotients
- Multipebble simulations for alternating automata (extended abstract)
- Simulation Relations for Alternating Parity Automata and Parity Games
- scientific article; zbMATH DE number 1954381 (Why is no real title available?)
- scientific article; zbMATH DE number 1754630 (Why is no real title available?)
- Topological characterisation of multi-buffer simulation
- Multi-buffer simulations for trace language inclusion
- Ramsey-based inclusion checking for visibly pushdown automata
- Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata
- Enhancing Simulation for Checking Language Containment
- Simulations in rank-based Büchi automata complementation
- Mediating for reduction (on minimizing alternating Büchi automata)
This page was built for publication: Simulation relations for alternating Büchi automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q557801)
