Category Theory

forCompositional Verification
Kazuki Watanabe
Clovis Eberhart]-

Kazuyuki Asada"
Ichiro Hasro2

Category Theory

forCompositional Verification Models
Kazuki Watanabe
Clovis Eberhart]-

Kazuyuki Asada"
2
Ichiro Hasro

1,

for

Category Theory
ModelsCompositional Verification
1, 2

Kazuki Watanabe

Clovis Eberhart]-

Kazuyuki Asada"
2
Ichiro Hasro

1,

Markov Decision
Processes

Plancategorical side
Semantics

syntax
-O

0--

Y/·&I

S - />O-O·~

7morphism 3-2 in $O
O-seting
lobidirectionalaWeget( free+anicesyntax)

algorithm froma

categorical approach.

Markov Decision Processes

Definition: "graph-like" structure with actions probabilities and rewards,action91g:↳- P1 nreward

Pa

↳

>

,I,1a1r⑳
9, mai-:,coalgebras
X>-(0X)*(where IPr e=

dayxQ,. . . ,an))

S,

an>
ang

transition ex, mnPrimn

probability

Scheduler choice of action for each state↳
expected reward from g to of:;-- -s
9 O&-is↑ -i>--roblem:given of gi qf,,,

find the maximum expected reward fromq;

toof.

,

MDPs

Open---i--R--........

- - -

S:0 ,4luYit5))· iii
8S,:0 1
2 :05>
.

.

-OI

↑

open

1 :0ends

7

0.
1:.

B.

a.

3-

2 :0 1.

5:0: 0 .1

2:0,:,

I:0 3.

05.

1:0,..

↓-- . . .

- - -

3
"MDP"

-- -I

5II,

↓-

2

2:0I

-----I-B
interface

of OMDPs

Composition
composition-i--.....
-'---- ----- ---- - -&R :0 4,

lu-OI, 13-2 :05:0.

.

-o[p ~aTto:os))

L =0,

B

0 .7 .
1::0.

- - -,
-22.

:0--,

5I

1:0,: 0 .1

..

: 05

I. . .

-·: 0. 3I.

identities:....

·S(I,IO
2:0.

:
inT

I

--=- . .
-Lemma:

I

2 :0 1

52:0-5LI

DP :forms a-objects:-

natural numbers-morphisms m -ncategory.

=:

OMDPs

with m (n) open ends on the left(rightof OMDPs

Composition
composition-i--.....
-'---- ----- -- -- - -&R :0 4,lu

2 :05,

I

S(I:0 1-.

-oos))

B

0 .7 .
1::0.

- - -.

:0--:5..

05

I- - -i--

....

...

-Y

I

1:0,

: 0 .1,: 0. 3I.

identities:>
-O
2:0.

SenI

-

.....

--,>
> -->---

Lemma:

2 :0 1

52:0-I,>-22I.

[p ~aT
to:LI

DP :forms a-objects:- >===

natural numbers-morphisms m -ncategory.

:OMDPswith m (n) open ends on the left(rightTrace of OMDPs

II5) T-----

R :0 4.............
S,lu

2 :05.

,:0 1

O-:0.

-O
B

2:0IO.

.

a.

: 0 .1-

2 :0 1,:0 3.

: Mi
70.
1:

I

2:0,:5:0.

5

1:0,05..

↓I-

Lemma:.

.....

MDPformsa--traced----symmetric monoidal category (TSMC) .

Semantics of OMDPs

compute maximum expected reward compositionallypossible expected rewards from entries to exits

Towe,need to know all.

'--...-.

....
>->-↳

Probabilities : RP op (i k);,Expected rewardTo:= RPas(i j) RP(j k,,ERM, or (i k,=Eli j) RPr(j k,compute expected rewards compositionally-expected rewards-reachability probabilities,,weneed+RPas(i j) ER(j k,toknow;,Semantic

Categoryfor OMDPs

of $ :
Definition
objects natural numbers-morphisms man (sets of mappings [n] > TPR [m]:-:where-PRX <(px rxxex1z
xexx
=s,

1 , x Ex

M53.

px >0

rewardprobablya,px=0> rx ==0]

Probabilistic>
position fim:--Pfig(irfig(i,,k)
k=nPf

,

(igin- p>,j)pg(j k),(i+k)
re(ipfj)rg(j k)= j) pg(j,,,,Trace in Semantics

-->
-->

↑J

RPf:

>

--...
-

I

Pf( 11...

,:Pflum)Pf(i )Jj,Pf(n 1)..

.

,pf(n m),I (sameforefin(pm) H(rp(f) (n -D) i:Trac

RPf=same/port] ao

RPtrp(f)=ERf)=RPthrough

ERthrough CRP

TSMC.
emma:

$ isRP ina

RPloop" RPortinERin][RPloop ERJER

Trace in Semantics(observations by P -A Mellies and T Seiller.

We can think of.

.

RPf and ERf(1) (h) (ELi)+Re=

asa(E). (i)=single matrix of elements of(petfiel=en: enta

RfRin

Roop" RootRtr(f)S=Rthrough=[Rign]2

Interpretation of OMDPs-----A..,

Hmorphism 2 - 3 in $O>>--undOCD (i j)=,Ci ea set of.
.

2-mappings

TPM3)[CRP(i j) ERoli j)/o scheduler],,,

tracedmonoidal functor
symmetric
Ie-Dmmais:↳ Wecana.

compute expected rewards compositionally !

Bidirectionality
Int() :objects-X:+,X-) where X +, X-objects of C

-morphisms (X+, X -) + (y+ ,*-Y-identityy):.

,f ED(X + 04-,Y+0x↑+

IfI x-Adita

ide 1 idxxox-(X+, x 1 :onand Int-constructionxY-composition :X+:mx:x=Z+- Xz

Lemma : Int(C) isunit

M-- -compact closed,Int(C)((I , 1) , (x+, x >.

idx X+(x-,x+1) = Int(c)((I I) , (x+ 0X,=.

(x 0X+-,X+0x-)-,X 0x+-1)

Int-construction : example

n--------

O

1-&O-

D--O-oN--↑↓I>-..........

usefulness : case ofFO-O

graph

y"

JY>
-O

X-E

I·JY

modellingOin TSMC

EigO

in-CompCC+-

Int-construction : example

isn--------x+[O↑1--oN&O>-34+---yI" J>
D---↑-o>-I..........

usefulness : case ofFO-O

graph

modelling

Oin TSMC

EigO

in-CompCC

Jy+Y-

Algorithm
This work is

published inAlgorithm

to[-if a=MDM ,; M2 then=a...

M, B; [McD),#===single state computing MD is trivial

17&-!

compute [MD :lider if d trp (M'-ifa isCAV

Our-algorithm:

beats state of the art
when there is-performance increases
with>
--

repetition

degree of repetition

cannot handle

interfaces

inlargepracticeSyntax

Free

Formally,

openMDPs

areequivalence classes of (n↳ not so nice to reason aboutorprogramon

Also would be nice to reason with universal,Freesyntax Er (2):Casill pret allwith P =an,men,,,,R)

mul , . un -Simia-

Q E P.

[( , are n -- T

Realisation functor : R : Er(IMPP) > ODP

Lemma: R is fullm.

properties,,Sn↑1,1

reme: miAlgorithm+ (IMPP), OMDP-I D&+I

AlgoI, R :=I.

ate:SData :morphism fim >n in (IMPP)

a-Returns : I (f)if (f = fr ; f2)&return I(fe) ; I (f2)]fz) [return I(f )I(f2))
clif (f Tr (f'l) Ereturn Tr (I(f'(7)elif (f f=,,=elif If

defined inductively(by universal property-Lemma -Bo:(in depthgenerator) [enumerate all schedulers]

I-inductive-

canon

structure of f

be done while

I(g) for sub-MDPS

remembering

New heuristics from
Our

algorithm is inefficient------I>-eWhy:onlarge interfaces.

if for all other schedulers,
optimalpotentiallyexit with
it reaches at least
higher probability/reward=> number increases
exponentially with number of exits.

scheduler

one,,
Rot
Watanabe,andas Junges↳

givesound heuristic

acompositionality

toare to.

Curves forapproximate maximal reachability probability.

;

L,J(D B 1 B)
--,L

↓

-

( E- E,

CompositionalaD

New heuristics from
Our

algorithm is inefficient------

I>-......iWhy:onlarge interfaces.

if for all other schedulers,
optimalpotentiallyexit with
it reaches at least
higher probability/reward=> number increases
exponentially with number of exits.

schedulerone,,Rot
Watanabe,andas Junges↳

givesound heuristic

acompositionality

toare to.

Curves forapproximate maximal reachability probability.

,J -L
,

(D B 1 B)
--,

↓

E>
-

Compositionala-

D

If-

you're interested

Watanabe, E ., Asada , Hasro.
MFPS'21.

.

↳ best account of theCarXiv-

Compositional Approach to Parity Games

hasversion

categorical techniques used inappendices

Watanabe
Hasro, E Asada,.,ourapproachwithProbabilistic Model-Compositional
Checking.

of MDPs
CAV'23.
DiagramsString↳ gives algorithm and experimental results
Solution of MeanWatanabe, E Asada, Hasro - Compositional
Payoff Games by String Diagrams.

--.

.,

↳--

developsa"meager semantics"

Vegt, Hasoo Rot Junges. Pareto Curves for Compositionally Model
Checking String Diagrams of MDPs TACAS 24.
↳ develops
sound heuristic based
compositionality
Hasuo A
Lechenne, E
Compositional
Approach to Petri Nets CMCS'24

Watanabe, van der,,--,--a-.,↳interestingon.

.

caseof Petri nets,Conclusioncategorical side-lsemantics

syntax-...
-SO ---C) - J

10 ------

get-sidealgorithmicWe↑'morphism 2-3 in $

mya

nice

algorithm fromacategorical approach.

-Future work

-general framework for compositional syntax-general framework for semantics of compositional systems(based onopen coalgebras