Sequential Value Passing Yields a Kleene Theorem for Processes

Jos C.M. Baeten; Bas Luttik

doi:10.1007/978-3-031-61716-4_1

Sequential Value Passing Yields a Kleene Theorem for Processes

Jos C.M. Baeten (Corresponding author)
, Bas Luttik

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

1 Citation (SciVal)

3 Downloads (Pure)

Abstract

Communication with value passing has received ample attention in process theory. Value passing through a sequential composition has received much less attention. In recent work, we found that sequential value passing is the essential ingredient to prove the analogue of the classical theorem of the equivalence of pushdown automata and context-free grammars in a setting of interactive processes and bisimulation. Subsequently, we found that the treatment of sequential value passing in the process setting can be simplified considerably. We report on this simplification here, and find another application of sequential value passing, viz. a Kleene theorem for processes.

Original language	English
Title of host publication	Logics and Type Systems in Theory and Practice
Subtitle of host publication	Essays Dedicated to Herman Geuvers on The Occasion of His 60th Birthday
Editors	Venanzio Capretta, Robbert Krebbers, Freek Wiedijk
Publisher	Springer
Chapter	1
Pages	1-16
Number of pages	16
ISBN (Electronic)	978-3-031-61716-4
ISBN (Print)	978-3-031-61715-7
DOIs	https://doi.org/10.1007/978-3-031-61716-4_1
Publication status	Published - 22 May 2024

Publication series

Name	Lecture Notes in Computer Science
Volume	14560 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

Keywords

bisimilarity
context-free grammar
Kleene theorem
process theory
pushdown automaton
sequential value passing

Access to Document

10.1007/978-3-031-61716-4_1

Cite this

Baeten, J. C. M., & Luttik, B. (2024). Sequential Value Passing Yields a Kleene Theorem for Processes. In V. Capretta, R. Krebbers, & F. Wiedijk (Eds.), Logics and Type Systems in Theory and Practice: Essays Dedicated to Herman Geuvers on The Occasion of His 60th Birthday (pp. 1-16). (Lecture Notes in Computer Science; Vol. 14560 LNCS). Springer. https://doi.org/10.1007/978-3-031-61716-4_1

@inbook{e79d1147091b497eae242a47cfa6a621,

title = "Sequential Value Passing Yields a Kleene Theorem for Processes",

abstract = "Communication with value passing has received ample attention in process theory. Value passing through a sequential composition has received much less attention. In recent work, we found that sequential value passing is the essential ingredient to prove the analogue of the classical theorem of the equivalence of pushdown automata and context-free grammars in a setting of interactive processes and bisimulation. Subsequently, we found that the treatment of sequential value passing in the process setting can be simplified considerably. We report on this simplification here, and find another application of sequential value passing, viz. a Kleene theorem for processes.",

keywords = "bisimilarity, context-free grammar, Kleene theorem, process theory, pushdown automaton, sequential value passing",

author = "Baeten, \{Jos C.M.\} and Bas Luttik",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.",

year = "2024",

month = may,

day = "22",

doi = "10.1007/978-3-031-61716-4\_1",

language = "English",

isbn = "978-3-031-61715-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "1--16",

editor = "Venanzio Capretta and Robbert Krebbers and Freek Wiedijk",

booktitle = "Logics and Type Systems in Theory and Practice",

address = "Germany",

}

Baeten, JCM & Luttik, B 2024, Sequential Value Passing Yields a Kleene Theorem for Processes. in V Capretta, R Krebbers & F Wiedijk (eds), Logics and Type Systems in Theory and Practice: Essays Dedicated to Herman Geuvers on The Occasion of His 60th Birthday. Lecture Notes in Computer Science, vol. 14560 LNCS, Springer, pp. 1-16. https://doi.org/10.1007/978-3-031-61716-4_1

Sequential Value Passing Yields a Kleene Theorem for Processes. / Baeten, Jos C.M. (Corresponding author); Luttik, Bas.
Logics and Type Systems in Theory and Practice: Essays Dedicated to Herman Geuvers on The Occasion of His 60th Birthday. ed. / Venanzio Capretta; Robbert Krebbers; Freek Wiedijk. Springer, 2024. p. 1-16 (Lecture Notes in Computer Science; Vol. 14560 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Sequential Value Passing Yields a Kleene Theorem for Processes

AU - Baeten, Jos C.M.

AU - Luttik, Bas

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

PY - 2024/5/22

Y1 - 2024/5/22

N2 - Communication with value passing has received ample attention in process theory. Value passing through a sequential composition has received much less attention. In recent work, we found that sequential value passing is the essential ingredient to prove the analogue of the classical theorem of the equivalence of pushdown automata and context-free grammars in a setting of interactive processes and bisimulation. Subsequently, we found that the treatment of sequential value passing in the process setting can be simplified considerably. We report on this simplification here, and find another application of sequential value passing, viz. a Kleene theorem for processes.

AB - Communication with value passing has received ample attention in process theory. Value passing through a sequential composition has received much less attention. In recent work, we found that sequential value passing is the essential ingredient to prove the analogue of the classical theorem of the equivalence of pushdown automata and context-free grammars in a setting of interactive processes and bisimulation. Subsequently, we found that the treatment of sequential value passing in the process setting can be simplified considerably. We report on this simplification here, and find another application of sequential value passing, viz. a Kleene theorem for processes.

KW - bisimilarity

KW - context-free grammar

KW - Kleene theorem

KW - process theory

KW - pushdown automaton

KW - sequential value passing

UR - https://www.scopus.com/pages/publications/85195926532

U2 - 10.1007/978-3-031-61716-4_1

DO - 10.1007/978-3-031-61716-4_1

M3 - Chapter

AN - SCOPUS:85195926532

SN - 978-3-031-61715-7

T3 - Lecture Notes in Computer Science

SP - 1

EP - 16

BT - Logics and Type Systems in Theory and Practice

A2 - Capretta, Venanzio

A2 - Krebbers, Robbert

A2 - Wiedijk, Freek

PB - Springer

ER -