uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Bisimulation minimization of tree automata
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Algorithmic Program Verification)
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Algorithmic Program Verification)
2007 (English)In: International Journal of Foundations of Computer Science, ISSN 0129-0541, Vol. 18, no 4, 699-713 p.Article in journal (Refereed) Published
Place, publisher, year, edition, pages
2007. Vol. 18, no 4, 699-713 p.
National Category
Computer Science
URN: urn:nbn:se:uu:diva-227791DOI: 10.1142/S0129054107004929ISI: 000251316500004OAI: oai:DiVA.org:uu-227791DiVA: diva2:731305
Available from: 2008-10-31 Created: 2014-07-01 Last updated: 2014-07-01Bibliographically approved
In thesis
1. Reduction Techniques for Finite (Tree) Automata
Open this publication in new window or tab >>Reduction Techniques for Finite (Tree) Automata
2008 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Finite automata appear in almost every branch of computer science, for example in model checking, in natural language processing and in database theory. In many applications where finite automata occur, it is highly desirable to deal with automata that are as small as possible, in order to save memory as well as excecution time.

Deterministic finite automata (DFAs) can be minimized efficiently, i.e., a DFA can be converted to an equivalent DFA that has a minimal number of states. This is not the case for non-deterministic finite automata (NFAs). To minimize an NFA we need to compute the corresponding DFA using subset construction and minimize the resulting automaton. However, subset construction may lead to an exponential blow-up in the size of the automaton and therefore even if the minimal DFA may be small, it might not be feasible to compute it in practice since we need to perform the expensive subset construction.

To aviod subset construction we can reduce the size of an NFA using heuristic methods. This can be done by identifying and collapsing states that are equal with respect to some suitable equivalence relation that preserves the language of the automaton. The choice of an equivalence relation is a trade-off between the desired amount of reduction and the computation time since the coarser a relation is, the more expensive it is to compute. This way we obtain a reduction method for NFAs that is useful in practice.

In this thesis we address the problem of reducing the size of non-deterministic automata. We consider two different computation models: finite tree automata and finite automata. Finite automata can be seen as a special case of finite tree automata and all of the previously mentioned results concerning finite automata are applicable to tree automata as well. For non-deterministic bottom-up tree automata, we present a broad spectrum of different relations that can be used to reduce their size. The relations differ in their computational complexity and reduction capabilities. We also provide efficient algorithms to compute the relations where we translate the problem of computing a given relation on a tree automaton to the problem of computing the relation on a finite automaton.

For finite automata, we have extended and re-formulated two algorithms for computing bisimulation and simulation on transition systems to operate on finite automata with alphabets. In particular, we consider a model of automata where the labels are encoded symbolically and we provide an algorithm for computing bisimulation on this partial symbolic encoding.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2008. 65 p.
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 562
Finite automata, tree automata, bisimulation, minimization, simulation, composed bisimulation, composed simulation
National Category
Computer Science
Research subject
Computer Science
urn:nbn:se:uu:diva-9330 (URN)978-91-554-7313-6 (ISBN)
Public defence
2008-11-21, Room 2446, Polacksbacken, Lägerhyddsvägen 2D, Uppsala, 09:15 (English)
Available from: 2008-10-31 Created: 2008-10-31 Last updated: 2014-07-01Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Abdulla, Parosh AzizKaati, Lisa
By organisation
Computer Systems
In the same journal
International Journal of Foundations of Computer Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 199 hits
ReferencesLink to record
Permanent link

Direct link