Five Determinisation Algorithms

Rob van Glabbeek, Bas Ploeger

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

Abstract

Determinisation of nondeterministic finite automata is a well-studied problem that plays an important role in compiler theory and system verification. In the latter field, one often encounters automata consisting of millions or even billions of states. On such input, the memory usage of analysis tools becomes the major bottleneck. In this paper we present several determinisation algorithms, all variants of the well-known subset construction, that aim to reduce memory usage and produce smaller output automata. One of them produces automata that are already minimal. We apply our algorithms to determinise automata that describe the possible sequences appearing after a fixed-length run of cellular automaton 110, and obtain a significant improvement in both memory and time efficiency.
Original languageEnglish
Title of host publicationImplementation and Applications of Automata
EditorsOscar H. Ibarra, Bala Ravikumar
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Pages161-170
Number of pages10
ISBN (Electronic)978-3-540-70844-5
ISBN (Print)978-3-540-70844-5
DOIs
Publication statusPublished - 24 Jul 2008
EventThe 13th International Conference on Implementation and Application of Automata, 2008 - San Francisco, United States
Duration: 21 Jul 200824 Jul 2008
Conference number: 13

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin, Heidelberg
Volume5148
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceThe 13th International Conference on Implementation and Application of Automata, 2008
Abbreviated titleCIAA 2008
Country/TerritoryUnited States
CitySan Francisco
Period21/07/0824/07/08

Fingerprint

Dive into the research topics of 'Five Determinisation Algorithms'. Together they form a unique fingerprint.

Cite this