Can I read Simulations and Antichains for Efficient Handling of Finite Automata on EtoBox?

Simulations and Antichains for Efficient Handling of Finite Automata by Holík, Lukáš is a scholarly article available to read on EtoBox.

What is Simulations and Antichains for Efficient Handling of Finite Automata about?

This thesis is focused on techniques for finite automata and their use in practice, with the main emphasis on nondeterministic tree automata. This concerns namely techniques for size reduction and language inclusion testing, which are two problems that are crucial for many applications of tree automata. For size reduction of tree automata, we adapt the simulation quotient technique that is well established for finite word automata. We give efficient algorithms for computing tree automata simulations and we also introduce a new type of relation that arises from a combination of tree automata downward and upward simulation and that is very well suited for quotienting. The combination principle is relevant also for word automata. We then generalise the so called antichain universality and language inclusion checking technique developed originally for finite word automata for tree automata. Subsequently, we improve the antichain technique for both word and tree automata by combining it with the simulation-based inclusion checking techniques, significantly improving efficiency of the antichain method. We then show how the developed reduction and inclusion checking methods improve the me

Author

Holík, Lukáš

Published

2017

Language

EN