Thesis Details

Efficient Algorithms for Counting Automata

Bachelor's Thesis Student: Mikšaník David Academic Year: 2019/2020 Supervisor: Lengál Ondřej, Ing., Ph.D.
Czech title
Efektivní algoritmy pro práci s čítacími automaty
Language
English
Abstract

Counting automata (CAs) are classical finite automata extended with bounded counters. They still denote the class of regular languages but in a more compact way than finite automata. Since CAs are a recent model, there is a gap in the knowledge of efficient algorithms implementing various operations on the CAs. In this thesis, we mainly focus on an existing subclass of CAs called monadic counting automata (MCAs), i.e., CAs with counting loops on character classes, which are common in practice (e.g., detection of packets in network traffic, log analysis). For this subclass, we efficiently solve the emptiness and inclusion problems. Moreover, we provide two extensions of the class of MCAs (but not beyond the class of CAs) and efficiently solve the emptiness problem for them. MCAs naturally arise from regular expressions that are extended by the counting operator limited only to character classes. Thus our algorithm solving the inclusion problem of MCAs can be used in a new method for solving the inclusion problem of such regular expressions. We experimentally evaluated this method on regular expressions from a wide range of applications and compared it with the naive method. The experiments show that the method using our algorithm is less prone the explode. It also outperforms the naive method if the regular expressions contain counting operators with large bounds. As expected, for the easy cases, the naive method is still faster than the method based on our algorithm.

Keywords

finite automata, counting automata, emptiness problem, inclusion, regular expressions

Department
Degree Programme
Information Technology
Files
Status
defended, grade A
Date
10 July 2020
Reviewer
Committee
Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT), předseda
Kekely Lukáš, Ing., Ph.D. (DCSY FIT BUT), člen
Křivka Zbyněk, Ing., Ph.D. (DIFS FIT BUT), člen
Rogalewicz Adam, doc. Mgr., Ph.D. (DITS FIT BUT), člen
Španěl Michal, Ing., Ph.D. (DCGM FIT BUT), člen
Citation
MIKŠANÍK, David. Efficient Algorithms for Counting Automata. Brno, 2020. Bachelor's Thesis. Brno University of Technology, Faculty of Information Technology. 2020-07-10. Supervised by Lengál Ondřej. Available from: https://www.fit.vut.cz/study/thesis/23029/
BibTeX
@bachelorsthesis{FITBT23029,
    author = "David Mik\v{s}an\'{i}k",
    type = "Bachelor's thesis",
    title = "Efficient Algorithms for Counting Automata",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2020,
    location = "Brno, CZ",
    language = "english",
    url = "https://www.fit.vut.cz/study/thesis/23029/"
}
Back to top