Thesis Details
Minimization of Counting Automata
This works deals with size reduction of counting automata (CA). Counting automata extend the classical finite automata with bounded counters. This allows efficient handling of e.g. regular expressions with repetition: a{5,10}. In this thesis we discusses the simulation relation in CA, which allows us to reduce their size. We rely on classical simulation in finite automata, which we non-trivially extend to CA. The key difference lies in the necessity to simulate counters as well as states. To this end, we present the novel concept of parameterized simulation relation in CA, and propose methods for computing this relation and using it to reduce the size of a CA. The proposed methods have been implemented and their efficiency experimentally evaluated.
counting automaton, simulation, reduction of automata
Hrubý Martin, Ing., Ph.D. (DITS FIT BUT), člen
Malinka Kamil, Mgr., Ph.D. (DITS FIT BUT), člen
Očenášek Pavel, Mgr. Ing., Ph.D. (DIFS FIT BUT), člen
Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT), člen
@mastersthesis{FITMT24072,
author = "Matej Turcel",
type = "Master's thesis",
title = "Minimization of Counting Automata",
school = "Brno University of Technology, Faculty of Information Technology",
year = 2021,
location = "Brno, CZ",
language = "english",
url = "https://www.fit.vut.cz/study/thesis/24072/"
}