The quest for minimal quotients for probabilistic automata

Christian Eisentraut, H. Hermanns, Johann Schuster, Andrea Turini, Lijun Zhang

    Research output: Contribution to conferencePaperAcademic

    14 Citations (Scopus)

    Abstract

    One of the prevailing ideas in applied concurrency theory and verification is the concept of automata minimization with respect to strong or weak bisimilarity. The minimal automata can be seen as canonical representations of the behaviour modulo the bisimilarity considered. Together with congruence results wrt. process algebraic operators, this can be exploited to alleviate the notorious state space explosion problem. In this paper, we aim at identifying minimal automata and canonical representations for concurrent probabilistic models. We present minimality and canonicity results for probabilistic automata wrt. strong and weak bisimilarity, together with polynomial time minimization algorithms.
    Original languageEnglish
    Pages16-31
    Number of pages16
    DOIs
    Publication statusPublished - Mar 2013
    Event19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2013 - Rome, Italy
    Duration: 16 Mar 201324 Mar 2013
    Conference number: 19

    Conference

    Conference19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2013
    Abbreviated titleTACAS
    CountryItaly
    CityRome
    Period16/03/1324/03/13

    Keywords

    • EWI-27343
    • EC Grant Agreement nr.: FP7/295261
    • EC Grant Agreement nr.: FP7/318490
    • IR-101830
    • EC Grant Agreement nr.: FP7/318003
    • EC Grant Agreement nr.: FP7/2007-2013

    Fingerprint Dive into the research topics of 'The quest for minimal quotients for probabilistic automata'. Together they form a unique fingerprint.

    Cite this