Recursive process definitions with the state operator

J.C.M. Baeten, J.A. Bergstra

    Research output: Contribution to journalArticlePopular

    3 Citations (Scopus)
    77 Downloads (Pure)


    Investigates the defining power of finite recursive specifications over the theory with +(alternative composition) and .(sequential composition) and lambda (the state operator) over a finite set of states, and find that it is greater than that of the same theory without state operator. Thus, adding the state operator is an essential extension of BPA (the theory of processes over +,.). On the other hand, applying the state operator to a regular process again gives a regular process. As a limiting result in the other direction, the authors find that not all PA-processes (where also parallel composition || is present) can be defined over BPA plus state operator
    Original languageEnglish
    Pages (from-to)285-302
    JournalTheoretical Computer Science
    Issue number2
    Publication statusPublished - 1991


    Dive into the research topics of 'Recursive process definitions with the state operator'. Together they form a unique fingerprint.

    Cite this