Platzhalter für Bild, Bild auf Titelfolie hinter das Logo einsetzen Marcello Bonsangue, Stefan Milius, Alexandra Silva Coalgebras and Generalized Regular

Platzhalter für Bild, Bild auf Titelfolie hinter das Logo einsetzen

Marcello Bonsangue, Stefan Milius, Alexandra Silva

Coalgebras and Generalized Regular Expressions

IFIP WG 1.3 2013 | Stefan Milius | March 16 | S. 2

Regular Expressions

S. Kleene (1956): regular expressions are equivalent to deterministic automata

D. Kozen (1994): Kleene-Algebras axiomatize the equivalence of regular expressions.

Syntatic description of regular languages:

S. C. Kleene: Representation of events in nerve nets and finite automata, Automata Studies 1956

D. Kozen: A completeness theorem for Kleene algebras and the algebra of regular events, I&C 1994

Problem:


Does this work for other systems (i.e. coalgebras) in a generic way?

What does „regular language“ mean?

Calculus of „regular expressions“ for coalgebras?

Syntax and semantics?

Correct and complete axiomatization?

Decidability?


Does this work for other systems (i.e.coalgebras) in a generic way?





Decidability?


Rational Fixpoint = „Regular Languages“ for Coalgebras

Given.

Construction.

Theorems.

1.+2.: J. Adamek, S. Milius, J. Velebil: Iterative Algebras at Work, MSCS 2006

3.: S. Milius, A sound and complete calculus for finite stream circuits, Proc. LICS 2010.


Examples


Does this work for coalgebras

in a generic way?





Decidability?


Expression calculi for bisimilarity

M. Bonsangue, J. Rutten, A. Silva et al.:

Regular expressions for coalgebras for set functors F from an inductively defined class

„Kleene Theorem“

Correctness and completeness for F-behavioral equivalence

Decidability

Applications: - regular expressions- Milner‘s calculus for finite state processes- Simple Segala Systems- New calculi for behavioral equivalence of:

(1) weighted automata; (2) stratified systems; (3) Pnüeli-Zuck-Systems

A. Silva, M. Bonsangue, J. Rutten: Non-deterministic Kleene Coalgebras, LMCS 2010.

F. Bonchi, M. Bonsangue, J. Rutten, A. Silva: Quantitative Kleene Coalgebras, I&C 2011.

M. Bonsangue, G. Caltais, E.-I. Goriac, D. Lucanu, J. Rutten, A. Silva: A decision procedure for bisimilarity of generalized regular expressions, SBMF 2010.

♥


But what about language equivalence?

Example. R. Milner‘s calculus for finite state processes

R. Milner: A complete inference system for a class of regular behaviours, J. Comput. Syst. Sci., 1984.


But what about language equivalence?

Example. R. Milner‘s calculus for finite state processes

Theorem. Axioms 1.-4. are sound and complete for bisimilarity.

A. Rabinovich:

Theorem. Axioms 1.-5. are sound and complete for trace-congruence.

R. Milner: A complete inference system for a class of regular behaviours, J. Comput. Syst. Sci., 1984.

A. Rabinovich: A complete axiomatization for trace congruence of finite state behaviors, Proc. MFPS, 1994.


Does this work for coalgebras in general?

What does „language equivalence“ mean for coalgebras?


Towards language equivalence of coalgebras

Examples. (1) nondeterministic automata

But

The nondeterministic/weighted branching does not occur in the desired final coalgebra.

Observation.

(2) weighted automata M. P. Schützenberger: On the definition

of a family of automata, I & C, 1961

semiring

But


Coalgebraic Language Equivalence

Two ideas are combined:1. Generalized powerset construction:

Definition (language equivalence).

Theorem.

Silva, Bonchi, Bonsangue, Rutten: Generalizing the powerset construction, coalgebraically, Proc. FSTTCS 2010.


Coalgebraic Language Equivalene

Two ideas are combined:1. Generalized powerset construction

2. Final coalgebras and ½F in algebraic categories

S. Milius, A sound and complete calculus for finite stream circuits, Proc. LICS 2010.

Example. correct and complete calculus for linear circuits


Relating final coalgebras and rational fixpoints

M. Bonsangue, S. Milius, A. Silva: Sound and complete axiomatizations of coalgebraic language equivalence, ACM ToCL, 2013.

Assumptions.

Bisimilarity and language equivalence:

finite


What is this good for?

Adding axioms a la Rabinovich is possible for FT-coalgebras such that … !

Generic tools: abstract Kleene Theorem & Soundness + Completeness Theorems

Application: Weighted Automata- Concrete expression syntax- Kleene Theorem- New correct+complete axiomatization of weighted language equivalence- Special cases:

1. Rabinovich‘s result (for nondeterministic automata)

2. Calculus for linear circuits

Independent and almost at the same time:

algebraic characterization of rational power series

M. Bonsangue, S. Milius, A. Silva: Sound and complete axiomatizations of coalgebraic language equivalence, ACM ToCL, 2013.

Z. Esik, W. Kuich: Free iterative and iteration K-semialgebras, Algebra Univ., 2012.


Example

Koalgebren und die Axiome von Iteration | Dr. S. Milius | 24. Januar 201319


Conclusions + Future Work

Rational fixpoints characterize finite state behavior of coalgebras

Method+Framework for sound and complete generalized regular expression calculi for coalgebras

Adding axioms to obtain sound+complete calculus for language equivalence is „always“ possible (concrete example: weighted automata)

Future work Decidability Generic calculus:

(1) deterministic system type (functor F) from an inductively defined class

(2) generic branching type (monad T) Relationship to presentations of functor (e.g. Rob Myers‘ PhD thesis) Other concrete calculi (e.g. probabilistic systems)

Documents

Platzhalter für Bild, Bild auf Titelfolie hinter das Logo einsetzen Marcello Bonsangue, Stefan Milius, Alexandra Silva Coalgebras and Generalized Regular