Five determinisation algorithms

R.J. Glabbeek, van, B. Ploeger

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    20 Citations (Scopus)
    1 Downloads (Pure)

    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 Application of Automata (13th International Conference, CIAA 2008, San Francisco CA, USA, July 21-24, 2008, Proceedings)
    EditorsO.H. Ibarra, B. Ravikumar
    Place of PublicationBerlin
    PublisherSpringer
    Pages161-170
    ISBN (Print)978-3-540-70843-8
    DOIs
    Publication statusPublished - 2008

    Publication series

    NameLecture Notes in Computer Science
    Volume5148
    ISSN (Print)0302-9743

    Fingerprint

    Dive into the research topics of 'Five determinisation algorithms'. Together they form a unique fingerprint.

    Cite this