Some remarks on definability of process graphs

C.A. Grabmayer, J.W. Klop, B. Luttik

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review


We propose the notions of "density" and "connectivity" of infinite process graphs and investigate them in the context of the wellknown process algebras BPA and BPP. For a process graph G, the density function in a state s maps a natural number n to the number of states of G with distance less or equal to n from s. The connectivity of a process graph G in a state s is a measure for how many different ways "of going from s to infinity" exist in G. For BPA-graphs we discuss some tentative findings about the notions density and connectivity, and indicate how they can be used to establish some non-definability results, stating that certain process graphs are not BPA-graphs, and stronger, not even BPA-definable. For BPPgraphs, which are associated with processes from the class of Basic Parallel Processes (BPP), we prove that their densities are at most polynomial. And we use this fact for showing that the paradigmatic process Queue is not expressible in BPP.
Originele taal-2Engels
TitelCONCUR 2006 - Concurrency Theory (Proceedings 17th International Conference, Bonn, Germany, August 27-30, 2006)
RedacteurenC. Baier, H. Hermanns
Plaats van productieBerlin
ISBN van geprinte versie3-540-37376-4
StatusGepubliceerd - 2006

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743

Vingerafdruk Duik in de onderzoeksthema's van 'Some remarks on definability of process graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit