Structure-Constrained Process Graphs for the Process Semantics of Regular Expressions

Virtual seminars Computer Science: Joint ICE-TCS and GSSI - Clemens Grabmayer

  • 1.7.2020, 13:30 - 14:30


Schedule: 1 July, 13:30 GMT/15:30 Italian time
Virtual link:
Speaker: Clemens Grabmayer (GSSI, Italy) WWW:

Title: Structure-Constrained Process Graphs for the Process Semantics of Regular Expressions

Abstract: Milner (1984) introduced a process semantics for regular expressions as process graphs. Unlike for the language semantics, where every regular language is the interpretation of some regular expression, there are finite process graphs that are not bisimilar to the process interpretation of any regular expression. For reasoning about graphs that are expressible by a regular expression it is desirable to have structural representations of process graphs in the image of the interpretation.

For `1-free' regular expressions, their process interpretations satisfy the structural property LEE (loop existence and elimination). But this is not always the case for general regular expressions, as we show by examples. Yet as a remedy, we describe the possibility to recover the property LEE for a close variant of the process interpretation. For this purpose we refine the process semantics of regular expressions to yield process graphs with 1-transitions, similar to silent moves for finite-state automata.

Vinsamlegast athugið að á viðburðum Háskólans í Reykjavík (HR) eru teknar ljósmyndir og myndbönd sem notuð eru í markaðsstarfi HR. Hægt er að nálgast frekari upplýsingar á eða með því að senda tölvupóst á netfangið:
Please note that at events hosted at Reykjavik University (RU), photographs and videos are taken which might be used for RU marketing purposes. Read more about this on our or send an e-mail: