You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Fundamenta Informaticae - Volume 192, issue 1

Purchase individual online access for 1 year to this journal.

Price: EUR 410.00
ISSN 0169-2968 (P)
ISSN 1875-8681 (E)

Impact Factor 2024: 0.4

Fundamenta Informaticae is an international journal publishing original research results in all areas of theoretical computer science. Papers are encouraged contributing:


- solutions by mathematical methods of problems emerging in computer science
- solutions of mathematical problems inspired by computer science.

Topics of interest include (but are not restricted to): theory of computing, complexity theory, algorithms and data structures, computational aspects of combinatorics and graph theory, programming language theory, theoretical aspects of programming languages, computer-aided verification, computer science logic, database theory, logic programming, automated deduction, formal languages and automata theory, concurrency and distributed computing, cryptography and security, theoretical issues in artificial intelligence, machine learning, pattern recognition, algorithmic game theory, bioinformatics and computational biology, quantum computing, probabilistic methods, & algebraic and categorical methods.

Global Types and Event Structure Semantics for Asynchronous Multiparty Sessions

Authors: Castellani, Ilaria | Dezani-Ciancaglini, Mariangiola | Giannini, Paola

Article Type: Research Article

Abstract: We propose an interpretation of multiparty sessions with asynchronous communication as Flow Event Structures . We introduce a new notion of asynchronous type for such sessions, ensuring the expected properties for multiparty sessions, including progress. Our asynchronous types, which reflect asynchrony more directly and more precisely than standard global types and are more permissive, are themselves interpreted as Prime Event Structures . The main result is that the Event Structure interpretation of a session is equivalent, when the session is typable, to the Event Structure interpretation of its asynchronous type, namely their domains of configurations are isomorphic.

Keywords: Communication-centric Systems, Communication-based Programming, Process Calculi, Event Structures, Multiparty Session Types

DOI: 10.3233/FI-242188

Citation: Fundamenta Informaticae, vol. 192, no. 1, pp. 1-75, 2024

Price: EUR 27.50

Relation-Algebraic Verification of Disjoint-Set Forests

Authors: Guttmann, Walter

Article Type: Research Article

Abstract: This paper studies how to use relation algebras, which are useful for high-level specification and verification, for proving the correctness of lower-level array-based implementations of algorithms. We give a simple relation-algebraic semantics of read and write operations on associative arrays. The array operations seamlessly integrate with assignments in computation models supporting while-programs. As a result, relation algebras can be used for verifying programs with associative arrays. We verify the correctness of an array-based implementation of disjoint-set forests using the union-by-rank strategy and find operations with path compression, path splitting and path halving. All results are formally proved in Isabelle/HOL. This … Show more

Keywords: arrays, Kleene algebras, path compression, program verification, relation algebras, union-find

DOI: 10.3233/FI-242189

Citation: Fundamenta Informaticae, vol. 192, no. 1, pp. 77-120, 2024

Price: EUR 27.50
Show more