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, Bas Luttik

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

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	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer
Pages	1-16
Number of pages	16
DOIs	https://doi.org/10.1007/978-3-031-61716-4_1
Publication status	Published - 2024

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
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 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 1-16). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14560 LNCS). Springer. https://doi.org/10.1007/978-3-031-61716-4_1

Baeten, Jos C.M. ; Luttik, Bas. / Sequential Value Passing Yields a Kleene Theorem for Processes. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer, 2024. pp. 1-16 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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",

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

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "1--16",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

Baeten, JCM & Luttik, B 2024, Sequential Value Passing Yields a Kleene Theorem for Processes. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 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.; Luttik, Bas.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer, 2024. p. 1-16 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 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

Y1 - 2024

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 - http://www.scopus.com/inward/record.url?scp=85195926532&partnerID=8YFLogxK

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

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

M3 - Chapter

AN - SCOPUS:85195926532

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 16

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer

ER -

Baeten JCM, Luttik B. Sequential Value Passing Yields a Kleene Theorem for Processes. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer. 2024. p. 1-16. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-61716-4_1