Compositional Minimization in Span(Graph): Some Examples | Zendy

Piergiulio Katis | Zendy; N. Sabadini | Zendy; R. F. C. Walters | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Compositional Minimization in Span(Graph): Some Examples

Author(s) -

Piergiulio Katis,

N. Sabadini,

R. F. C. Walters

Publication year - 2004

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2004.08.025

Subject(s) - span (engineering) , mathematics , minification , graph , computer science , discrete mathematics , mathematical optimization , engineering , civil engineering

We study a class of examples of minimizing automata with respect to branching bisimulation in the context of the Span(Graph) model. Compositional minimization is particularly ecient for the class which includes the classical dining philospher problem and variants. The reason for the eciency is that finite subsets of the class generate finite submonoids of the bisimulation monoid. We indicate how this may be used in studying deadlock. In the case of the dining philosopher the critical fact is that (F · P)3 = (F · P)2 in the bisimulation monoid, where F is the fork and P

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research