Algebraic hierarchical decomposition of finite state automata : comparison of implementations for Krohn-Rhodes Theory

Attila Egri-Nagy, C.L. Nehaniv

    Research output: Contribution to journalArticlepeer-review

    8 Citations (Scopus)
    50 Downloads (Pure)

    Abstract

    The hierarchical algebraic decomposition of finite state automata (Krohn-
    Rhodes Theory) has been a mathematical theory without any computational
    implementations until the present paper, although several possible and promising practical applications such as automated object-oriented programming in software development [5], formal methods for understanding in artificial intelligence [6], a widely applicable integer-valued complexity measure [8,7], have been described. As a remedy for the situation, our new implementation, described here, is freely available [2] as open-source software. We also present two different computer algebraic implementations of the Krohn-Rhodes decomposition, the V [T and holonomy decompositions [4,3], and compare their efficiency in terms of the number of hierarchical levels in the resulting cascade decompositions.
    Original languageEnglish
    Pages (from-to)315-316
    JournalLecture Notes in Computer Science (LNCS)
    Volume3317
    Publication statusPublished - 2005

    Fingerprint

    Dive into the research topics of 'Algebraic hierarchical decomposition of finite state automata : comparison of implementations for Krohn-Rhodes Theory'. Together they form a unique fingerprint.

    Cite this