Reducing Nondeterministic Tree Automata by Adding Transitions

Ricardo Manuel de Oliveira Almeida

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We introduce saturation of nondeterministic tree automata, a technique that consists of adding new transitions to an automaton while preserving its language. We implemented our algorithm on minotaut - a module of the tree automata library libvata that reduces the size of automata by merging states and removing superfluous transitions - and we show how saturation can make subsequent merge and transition-removal operations more effective. Thus we obtain a Ptime algorithm that reduces the size of tree automata even more than before. Additionally, we explore how minotaut alone can play an important role when performing hard operations like complementation, allowing to both obtain smaller complement automata and lower computation times. We then show how saturation can extend this contribution even further. We tested our algorithms on a large collection of automata from applications of libvata in shape analysis, and on different classes of randomly generated automata.
Original languageEnglish
Title of host publication1th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, rm Telč, Czech Republic, 21st-23rd October 2016
EditorsJan Bouda, Lukáš Holík, Jan Kofroň, Jan Strejček, Adam Rambousek
PublisherOpen Publishing Association
Pages33-51
Number of pages19
Volume233
DOIs
Publication statusPublished - 13 Dec 2016
Event11th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science - Telč, Czech Republic
Duration: 21 Oct 201623 Oct 2016
Conference number: 11

Publication series

NameElectronic Proceedings in Theoretical Computer Science
PublisherOpen Publishing Association
ISSN (Electronic)2075-2180

Conference

Conference11th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Abbreviated titleMEMICS 2016
Country/TerritoryCzech Republic
CityTelč
Period21/10/1623/10/16

Fingerprint

Dive into the research topics of 'Reducing Nondeterministic Tree Automata by Adding Transitions'. Together they form a unique fingerprint.

Cite this