Advanced automata minimization

DOI10.1145/2429069.2429079zbMath1301.68171arXiv1210.6624OpenAlexW1979078717MaRDI QIDQ2931784

Lorenzo Clemente, Richard Mayr

Publication date: 27 November 2014

Published in: Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1210.6624

zbMATH Keywords

simulationminimizationBüchi automata

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (15)

Parity game reductions ⋮ On the power of finite ambiguity in Büchi complementation ⋮ Simulation relations and applications in formal methods ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Minimization of Visibly Pushdown Automata Using Partial Max-SAT ⋮ Forward Bisimulations for Nondeterministic Symbolic Finite Automata ⋮ Coinductive Algorithms for Büchi Automata ⋮ Organising LTL monitors over distributed systems with a global clock ⋮ Complementing Büchi Automata with Ranker ⋮ Multi-buffer simulations: decidability and complexity ⋮ Incremental dead state detection in logarithmic time ⋮ Sky is not the limit. Tighter rank bounds for elevator automata in Büchi automata complementation ⋮ Simulations in rank-based Büchi automata complementation ⋮ Topological Characterisation of Multi-Buffer Simulation

This page was built for publication: Advanced automata minimization