Context-Free Languages
via
Coalgebraic Trace Semantics
Ichiro Hasuo

Bart Jacobs

Radboud University Nijmegen, the Netherlands

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 1/31

Historical remarks
Coalgebraic treatment of trace semantics fornon-deterministic systems...
Introduction● Historical remarks● OverviewnMotivating example: CFG

Power & Turi, CTCS’99
u For P(1 + Σ × −)-coalgebras.

Main technical resultu Working in Kleisli category SetsP .

Monad structures in languages
Application of main result
Generalization: probabilistic
systemsn

BJ, CMCS’04
u Final coalgebra in Sets yields weakly final coalgebra in

Future work and conclusions

Rel = SetsP .
u First result for general functors.
n

IH & BJ, CALCO’05

IH & BJ, CALCO-jnr

u Current work...

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 2/31

OverviewnIntroduction

Initial algebra in Sets yields final coalgebra in Rel● Overview

u Finite trace semantics for non-deterministic systems

Motivating example: CFG

u Application: context-free grammars/languages● Historical remarks

u Rel ∼
= SetsP , Kleisli category

Main technical result
Monad structures in languages
Application of main result
Generalization: probabilistic
systemsn

Same for subdistribution monad D, instead of P

Future work and conclusionsu Finite trace semantics for probabilistic systems
u In Proc. CALCO-jnr.

n(Co)algebraic formulation of CFG/CFLu Monad structure, “fundamental span” of languages

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 3/31

Context-free grammars: example
n Terminal symbols: 0, x, s, =, ∧, ¬, ∀Introduction
Motivating example: CFG

n Non-terminal symbols: T, Q, F
n Generation rules:● Context-free grammars:

TI0
TIx
T I sT

example● CFG as coalgebra● CFG/CFL, coalgebraically
Main technical result

Q I ∀xF I T=TF I QFF I F∧FF I ¬F

Monad structures in languages
Application of main result
Generalization: probabilistic
systems∀x¬(s(x) = 0) is generated as:F

Future work and conclusions

F

Q
∀

x

¬

F
= T

T
s T

0

x

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 4/31

CFG as coalgebra¡

P (Σ + X)
IntroductionnMotivating example: CFG

c

∗

¢

in Sets● Context-free grammars:"

X : non-terminals
Σ : terminals#

X

example● CFG as coalgebra● CFG/CFL, coalgebraically
Main technical result
Monad structures in languages
Application of main result

n E.g.

©

Generalization: probabilistic
systems

T=T, QF, F∧F, ¬FªF

Future work and conclusionsn

Question
How can we characterize a context-free language
generated by a CFG?

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 5/31

CFG/CFL, coalgebraically
PF X
c
X

Introduction
Motivating example: CFG● Context-free grammars:
example● CFG as coalgebra● CFG/CFL, coalgebraically
Main technical result

where F = (Σ + −)∗Observationsn Initial F -algebra= set of finite parse trees like

Monad structures in languages=

Application of main resultsGeneralization: probabilistic
systems

0x

Future work and conclusionsn Final F -coalgebra =initial F -algebra + (infinite parse trees, undesired)n c is a coalgebra in Kleisli category SetsP .
n Equivalently, c is a coalgebra in Rel, because

c : X → PF X
R ½ X × FXCALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 6/31

Main technical result
Let F be a shapely functor in Sets (details later).
FA
Introduction
Motivating example: CFG

LetMain technical result∼= α

be the initial F -algebra in Sets.

A● Main technical result● Finite trace of
non-deterministic systems● History of proofs● Proof of main result, shortest
version● Possibly infinite traces

TheoremMonad structures in languages

PF A

Application of main result{−}

Generalization: probabilistic
systems
Future work and conclusions

FA

CoalgebraFA
α−1
Ain Sets

CALCO 2005, Swansea, UK. 9th September 2005

i.e.

is final in SetsP .
A
in SetsP

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 7/31

Finite trace of non-deterministic systems
Hence, a non-deterministic coalgebra in Sets
Introduction
Motivating example: CFG
Main technical result● Main technical result● Finite trace of
non-deterministic systems● History of proofs

PF X
has a unique finite trace X

c

ft(c)
PA

X

● Proof of main result, shortest
version● Possibly infinite traces
Monad structures in languages
Application of main resultsuch that:

Generalization: probabilistic
systems
Future work and conclusions

In SetsP

FX

F (ft(c))∼= {−} ◦ α−1c
X

CALCO 2005, Swansea, UK. 9th September 2005

FA

ft(c)

A

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 8/31

History of proofs
Three versions of proofs for the main result...
Introductionn Nov. 2004, by IH

Motivating example: CFG
Main technical result● Main technical result● Finite trace of
non-deterministic systems● History of proofs

In submitted paper/technical report.
3 pages, lengthy, hard to get intuition.

● Proof of main result, shortest
version● Possibly infinite traces
Monad structures in languages
Application of main result
Generalization: probabilistic
systems
Future work and conclusions

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 9/31

History of proofs
Three versions of proofs for the main result...
Introductionn Nov. 2004, by IH

Motivating example: CFG

In submitted paper/technical report.
3 pages, lengthy, hard to get intuition.

Main technical result● Main technical result● Finite trace of
non-deterministic systems● History of proofs● Proof of main result, shortestn March 2005, by IH/BJ

version● Possibly infinite traces
Monad structures in languages
Application of main result

In the proceedings, what you have at hand.
2 pages, concrete, intuitive.
Easy to generalize.

Generalization: probabilistic
systems
Future work and conclusions

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 9/31

History of proofs
Three versions of proofs for the main result...
Introductionn Nov. 2004, by IH

Motivating example: CFG

In submitted paper/technical report.
3 pages, lengthy, hard to get intuition.

Main technical result● Main technical result● Finite trace of
non-deterministic systems● History of proofs● Proof of main result, shortestn March 2005, by IH/BJ

In the proceedings, what you have at hand.
2 pages, concrete, intuitive.
Easy to generalize.

version● Possibly infinite traces
Monad structures in languages
Application of main result
Generalization: probabilistic
systemsn June 2005, by BJ

Future work and conclusions

Latest version.
2 lines. Made IH depressed.
Presented now.

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 9/31

Proof of main result, shortest version

Introduction
Motivating example: CFG
Main technical result● Main technical result● Finite trace of
non-deterministic systems● History of proofs● Proof of main result, shortest
version● Possibly infinite traces
Monad structures in languages
Application of main result
Generalization: probabilistic
systems
Future work and conclusions

Sets

⊥

∼
=

SetsP

(SetsP )op

Kleisli construction and self-duality.
Note that: SetsP ∼= Rel .

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 10/31

Proof of main result, shortest version

Introduction
Motivating example: CFG
Main technical result● Main technical result● Finite trace of
non-deterministic systems● History of proofs● Proof of main result, shortest
version● Possibly infinite traces
Monad structures in languages
Application of main result
Generalization: probabilistic
systems

Sets

Future work and conclusions

⊥

SetsP

∼
=

(SetsP )op(FP )opF[Power & Turi, CTCS’99]
Due to the distributive law F P ⇒ PF (power law),
F lifts to FP on SetsP .
CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 10/31

Proof of main result, shortest version

Introduction
Motivating example: CFG
Main technical result● Main technical result● Finite trace of
non-deterministic systems● History of proofs¡

Alg(F )

● Proof of main result, shortest
version● Possibly infinite traces

Alg (FP )Monad structures in languages

op¢

Application of main result
Generalization: probabilistic
systems

Sets

Future work and conclusionsF

CALCO 2005, Swansea, UK. 9th September 2005

⊥

SetsP

∼
=

(SetsP )op(FP )op

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 10/31

Proof of main result, shortest version

Introduction
Motivating example: CFG
Main technical result● Main technical result● Finite trace of
non-deterministic systems● History of proofs

Alg(F )

● Proof of main result, shortest
version● Possibly infinite traces¡

Alg (FP )⊥Monad structures in languages

op¢

Application of main result
Generalization: probabilistic
systems

Sets

Future work and conclusions

⊥

SetsP

∼
=

(SetsP )op(FP )opF
By a standard result the adjunction lifts.
See e.g. [Hermida & BJ, Inf. & Comp., 1998].

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 10/31

Proof of main result, shortest version¡

Introduction
Motivating example: CFG
Main technical result● Main technical result● Finite trace of
non-deterministic systems● History of proofs

Alg(F )

● Proof of main result, shortest
version● Possibly infinite traces

CoAlg(FP )∼=¡Alg (FP )⊥Monad structures in languages

¢op

op

¢

Application of main result
Generalization: probabilistic
systems

Sets

Future work and conclusions

⊥

SetsP

∼
=

(SetsP )op(FP )op

F
Initial object is preserved by left adjoints.
Q.E.D.

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 10/31

Possibly infinite traces
PF X
Introductionn To eachc, our finality result assigns its

X

Motivating example: CFG
Main technical result● Main technical result● Finite trace of
non-deterministic systems● History of proofs

finite trace● Proof of main result, shortest
version● Possibly infinite traces

ft(c)
X

PA

,

where A is the initial F -algebra.

Monad structures in languages
Application of main result
Generalization: probabilistic
systems
Future work and conclusionsnPossibly infinite trace

trace(c)X

PZ,

where Z is final F -coalgebra, is given by [BJ, CMCS’04].
Not via finality, but via (weak finality + “biggest” choice).
n Their relationship is investigated in our paper.

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 11/31

Introduction
Motivating example: CFG
Main technical result

Intermezzo:

Monad structures in languages● Fundamental span oflanguages
Application of main result

Monad structures in languages

Generalization: probabilistic
systems
Future work and conclusions

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 12/31

Fundamental span of languagesnΣ∗

set of flat strings over ΣnΣ4Initial (Σ + −)∗ -algebra,
set of finite parse trees over Σ

Introduction
Motivating example: CFG
Main technical result

e.g.
=Monad structures in languages● Fundamental span oflanguagess0Application of main resultx

Generalization: probabilistic
systems
Future work and conclusionsnΣ∧Final (Σ + −)∗ -coalgebra,
Σ4 plus infinite parse trees

e.g.
=
s

0
s

..
.

All of these constructions are monads:
Σ 7→ Σ∗CALCO 2005, Swansea, UK. 9th September 2005

Σ 7→ Σ4

Σ 7→ Σ∧Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 13/31

Fundamental span of languages
For functor F = (Σ + −)∗ ,Introduction
Motivating example: CFG
Main technical result

F -algebra

initial
F -algebra

final
F -coalgebra

Σ∗

Σ4

Σ∧

Monad structures in languages● Fundamental span oflanguages
Application of main result
Generalization: probabilistic
systems

flattening
by initiality

canonical
embedding

Future work and conclusions=
sx = 0

s

=
0

x

s

0
x

Both arrows are maps of monads.

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 14/31

Introduction
Motivating example: CFG
Main technical result

Back to coalgebraic trace semantics...

Monad structures in languages
Application of main result● CFL via trace semantics● Non-deterministic automata● Alternative construction
Generalization: probabilistic
systems
Future work and conclusions

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 15/31

CFL via trace semantics

Introduction

For F = (Σ + −)∗ and a CFG

PF X
c

,

X

Motivating example: CFG
Main technical result
Monad structures in languages

n By finality result in SetsP , we obtain

Application of main result● CFL via trace semantics● Non-deterministic automata● Alternative construction

In Sets

Generalization: probabilistic
systems

ft(c)

¡

4

¢

X

P Σ

x

{generated parse trees from x}

Future work and conclusionsn Generated language is obtained by flattening:X

CALCO 2005, Swansea, UK. 9th September 2005

ft(c)

¡

P Σ

4

¢

P(flattening)

¡

P Σ

∗

¢

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 16/31

Non-deterministic automata
Here is another application...
Introduction
Motivating example: CFG

n Non-deterministic automaton:

Main technical result

PF X

Monad structures in languages

where F = 1 + Σ × − ,list functor

Application of main result● CFL via trace semantics● Non-deterministic automata

X● Alternative construction
Generalization: probabilistic
systems
Future work and conclusionsn For F = 1 + Σ × −,initial F -algebra is Σ∗ (lists).

n By our finality result we obtainft(c)CALCO 2005, Swansea, UK. 9th September 2005

accepted language :
¡

∗

¢

X

P Σ

x

(language accepted by state x)Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 17/31

Alternative constructionn Non-deterministic automaton:

P(1 + Σ × X)

2 × (PX)Σ

Introduction
Motivating example: CFG
Main technical result
Monad structures in languages
Application of main result● CFL via trace semantics● Non-deterministic automata

Xn Bartels’ generalized coinduction scheme [CMCS’01]
applies to● Alternative construction

GPX

Generalization: probabilistic
systems
Future work and conclusions

X

where G = 2 × (−)Σ ,deterministic automaton functor

n It also gives the map

¡

∗

¢

X

P Σ

x

(language accepted by state x)

n Connection is to be investigated.
CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 18/31

Introduction
Motivating example: CFG
Main technical result

Trace semantics

Monad structures in languages
Application of main result
Generalization: probabilistic

for probabilistic systems

systems● Generalization (in Proc. of
CALCO-jnr.)● Subdistribution monad● Trace semantics forprobabilistic systems● Example: probabilistic
systems● How does the proof(in Proc. CALCO-jnr.)

generalize?
Future work and conclusions

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 19/31

Generalization (in Proc. of CALCO-jnr.)

Introduction
Motivating example: CFG

The finality result above holds forn powerset monad P, andn endofunctor F which is shapely [C. Barry Jay], i.e.

Main technical result

F ::= id | Σ | F × F |Monad structures in languages

systems● Generalization (in Proc. ofFiiApplication of main result
Generalization: probabilistica

How about other monads/functors?

CALCO-jnr.)● Subdistribution monad● Trace semantics forprobabilistic systems● Example: probabilistic
systems● How does the proof
generalize?
Future work and conclusions

Currently we have obtained a result for
subdistribution monad D

instead of P

which gives trace distribution of probabilistic systems.
In Proc. of CALCO-jnr.

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 20/31

Subdistribution monad
DX = {d : X → [0, 1] |Xd(x) ≤ 1}x∈X

Introduction
Motivating example: CFG
Main technical result
Monad structures in languages

PF X

Application of main result
Generalization: probabilistic
systems

Coalgebra● Generalization (in Proc. of:Non-deterministic system:

Probabilistic systemX

CALCO-jnr.)● Subdistribution monad● Trace semantics forprobabilistic systems● Example: probabilistic
systems● How does the proof
generalize?

DF X
Coalgebra

Future work and conclusions

CALCO 2005, Swansea, UK. 9th September 2005

X

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 21/31

Trace semantics for probabilistic systems
Again we move to Kleisli category SetsD :Introduction
Motivating example: CFG
Main technical result
Monad structures in languages
Application of main result
Generalization: probabilistic

SetsD







objectthat of Sets

arrow

X→Y
X → DYin SetsD
in Sets

systems● Generalization (in Proc. of
CALCO-jnr.)● Subdistribution monad● Trace semantics forprobabilistic systems● Example: probabilistic
systems● How does the proof
generalize?
Future work and conclusions

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 22/31

Trace semantics for probabilistic systems
Let F be a shapely functor in Sets.
FA
Introduction
Motivating example: CFG

LetMain technical result∼= α

be the initial F -algebra in Sets.

A

Monad structures in languages
Application of main result
Generalization: probabilistic
systems● Generalization (in Proc. ofTheorem

CALCO-jnr.)● Subdistribution monad

DF A● Trace semantics forprobabilistic systems● Example: probabilistic

ηDsystems● How does the proof
generalize?
Future work and conclusions

FA

CoalgebraFA
α−1
Ain Sets

CALCO 2005, Swansea, UK. 9th September 2005

i.e.

is final in SetsD .
A
in SetsD

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 23/31

Trace semantics for probabilistic systems
Hence, a probabilistic coalgebra in Sets
Introduction
Motivating example: CFG
Main technical result
Monad structures in languages
Application of main result

DF X

ft(c)

has a unique finite trace X

c

DA

X

Generalization: probabilistic
systems● Generalization (in Proc. of
CALCO-jnr.)● Subdistribution monad● Trace semantics forsuch that:probabilistic systems● Example: probabilistic
systems● How does the proof
generalize?
Future work and conclusions

In SetsD

FXFA∼= η D ◦ α−1c
X

CALCO 2005, Swansea, UK. 9th September 2005

F (ft(c))

ft(c)

A

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 24/31

Example: probabilistic systems
DF X
cIntroduction
Motivating example: CFG

where F = 1 + Σ × − ,list functor

X

Main technical result
Monad structures in languages
Application of main result

ExampleGeneralization: probabilistic
systems● Generalization (in Proc. of
CALCO-jnr.)● Subdistribution monadx● Trace semantics forprobabilistic systems● Example: probabilistic(a, 13 )systems● How does the proof

2
9

generalize?
Future work and conclusions(a, 1)(a, 13 )

z

y
1
2

X

(a, 12 )c(x) =

X
7→ 2/9


(a,
y)
→
7
1/3


(a, z) →7
1/3
c(y) = · · ·Remaining 1/9 of c(x):CALCO 2005, Swansea, UK. 9th September 2005

probability of deadlock

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 25/31

Example: probabilistic systems
n For F = 1 + Σ × −,initial F -algebra is Σ∗ (lists).

Introduction
Motivating example: CFG
Main technical result

n GivenMonad structures in languages

DF X
c
,

by our finality result we obtain

X

Application of main result
Generalization: probabilistic
systems● Generalization (in Proc. of
CALCO-jnr.)● Subdistribution monadft(c) : X → D(Σ∗ )probability distribution on traces● Trace semantics forprobabilistic systems● Example: probabilistic
systems● How does the proof
generalize?
Future work and conclusions

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 26/31

Example: probabilistic systems
Example(a, 13 )x

IntroductionyMotivating example: CFG(a, 13 )Main technical result
Monad structures in languages(a, 1)

Application of main result

1
2

2
9

z

(a, 12 )X

Generalization: probabilistic
systems● Generalization (in Proc. of
CALCO-jnr.)● Subdistribution monad● Trace semantics forprobabilistic systems● Example: probabilistic
systems● How does the proof
generalize?
Future work and conclusions£¤

ft(c) (x) : hi 7→

2
9

a 7→

1
3

·

1
2

a2 7→

1
3

·

1
2

·

1
2

···

Remaining of ft(c) (x) is understood:
1/3 for livelock,
1/9 for deadlock

CALCO 2005, Swansea, UK. 9th September 2005£¤

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 27/31

How does the proof generalize?
n For
Introduction

u commutative monad T and

Motivating example: CFG

u shapely F ,Main technical result

we have distributive law F T ⇒ T F .

Monad structures in languages
Application of main result
Generalization: probabilistic
systemsn Distributive law F T ⇒ T F lifts F to Kleisli category of T .

[Power & Turi, CTCS’99]● Generalization (in Proc. of
CALCO-jnr.)● Subdistribution monad● Trace semantics forn Subdistribution monad D is commutative.

probabilistic systems● Example: probabilistic
systems● How does the proof
generalize?
Future work and conclusions

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 28/31

How does the proof generalize?
n For valuation monad
Introduction
Motivating example: CFG
Main technical result
Monad structures in languages

VX = RX , the proof works.

u SetsV is again self-dual.
u Cf. PX = 2X

Application of main result
Generalization: probabilistic
systems● Generalization (in Proc. of
CALCO-jnr.)● Subdistribution monad● Trace semantics forprobabilistic systems● Example: probabilisticn D ,→ V, “nice” submonad.

For example, distributive law F V ⇒ VF restricts to D:

systems● How does the proof
generalize?

FV

VF

FD

DF

Future work and conclusions

How “nice”? Yet to be investigated.

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 29/31

Future workn Other monads.
Introduction
Motivating example: CFG

Especially PD (with modification, [Varacca, LICS’02]),
which is of interest in concurrency theory.

Main technical result
Monad structures in languages
Application of main result
Generalization: probabilisticn Other functors.

systems
Future work and conclusions● Future work
● Conclusionsn Other base categories. On arbitrary toposes?

n CFG/CFL and pushdown automata.

n Parsing, which is (partial) inverse of flattening Σ 4 ³ Σ∗ .

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 30/31

Conclusionsn Initial algebra in Sets yields final coalgebra in

Rel = SetsP .

Introduction
Motivating example: CFG
Main technical result
Monad structures in languages
Application of main result
Generalization: probabilistic

u Trace semantics for non-deterministic systems
u CFG/CFL, non-deterministic automatan Initial algebra in Sets yields final coalgebra in Sets D .

systems
Future work and conclusions● Future worku Trace semantics for probabilistic systems● Conclusionsn (Co)algebraic structures in CFG/CFL.

CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 31/31

Conclusionsn Initial algebra in Sets yields final coalgebra in

Rel = SetsP .

Introduction
Motivating example: CFG
Main technical result
Monad structures in languages
Application of main result
Generalization: probabilistic

u Trace semantics for non-deterministic systems
u CFG/CFL, non-deterministic automatan Initial algebra in Sets yields final coalgebra in Sets D .

systems
Future work and conclusions● Future worku Trace semantics for probabilistic systems● Conclusionsn (Co)algebraic structures in CFG/CFL.
n The authors make each other depressed from time totime.

Thank you for your attention!
Contact: Ichiro Hasuo www.cs.ru.nl/∼ichiro ichiro@cs.ru.nl
CALCO 2005, Swansea, UK. 9th September 2005

Context-Free Languages via Coalgebraic Trace Semantics – Ichiro Hasuo, Nijmegen, NL - p. 31/31