Dominique Méry

Gabriel Ciobanu

This book constitutes the refereed proceedings of the 11th International Colloquium on Theoretical Aspects of Computing, ICTAC 2014 held in Bucharest, Romania, in September 2014. The 25 revised full papers presented together with three invited talks were carefully reviewed and selected from 74 submissions. The papers cover various topics such as automata theory and formal languages; principles and semantics of programming languages; theories of concurrency, mobility and reconfiguration; logics and their applications; software architectures and their models, refinement and verification; relationship between software requirements, models and code; static and dynamic program analysis and verification; software specification, refinement, verification and testing; model checking and theorem proving; models of object and component systems; coordination and feature interaction; integration of theories, formal methods and tools for engineering computing systems; service-oriented architectures: models and development methods; models of concurrency, security, and mobility; theories of distributed, grid and cloud computing; real-time, embedded, hybrid and cyber-physical systems; type and category theory in computer science; models for e-learning and education; case studies, theories, tools and experiments of verified systems; domain-specific modeling and technology: examples, frameworks and practical experience; challenges and foundations in environmental modeling and monitoring, healthcare, and disaster management.

11th International Colloquium, Bucharest, Romania, September 17-19, 2014. Proceedings

Theoretical Aspects of Computing – ICTAC 2014

Andrei Alexandru

In this book the authors present an alternative set theory dealing with a more relaxed notion of infiniteness, called finitely supported mathematics (FSM). It has strong connections to the Fraenkel-Mostowski (FM) permutative model of Zermelo-Fraenkel (ZF) set theory with atoms and to the theory of (generalized) nominal sets. More exactly, FSM is ZF mathematics rephrased in terms of finitely supported structures, where the set of atoms is infinite (not necessarily countable as for nominal sets). In FSM, 'sets' are replaced either by `invariant sets' (sets endowed with some group actions satisfying a finite support requirement) or by `finitely supported sets' (finitely supported elements in the powerset of an invariant set). It is a theory of `invariant algebraic structures' in which infinite algebraic structures are characterized by using their finite supports. After explaining the motivation for using invariant sets in the experimental sciences as well as the connections with the nominal approach, admissible sets and Gandy machines (Chapter 1), the authors present in Chapter 2 the basics of invariant sets and show that the principles of constructing FSM have historical roots both in the definition of Tarski `logical notions' and in the Erlangen Program of Klein for the classification of various geometries according to invariants under suitable groups of transformations. Furthermore, the consistency of various choice principles is analyzed in FSM. Chapter 3 examines whether it is possible to obtain valid results by replacing the notion of infinite sets with the notion of invariant sets in the classical ZF results. The authors present techniques for reformulating ZF properties of algebraic structures in FSM. In Chapter 4 they generalize FM set theory by providing a new set of axioms inspired by the theory of amorphous sets, and so defining the extended Fraenkel-Mostowski (EFM) set theory. In Chapter 5 they define FSM semantics for certain process calculi (e.g., fusion calculus), and emphasize the links to the nominal techniques used in computer science. They demonstrate a complete equivalence between the new FSM semantics (defined by using binding operators instead of side conditions for presenting the transition rules) and the known semantics of these process calculi. The book is useful for researchers and graduate students in computer science and mathematics, particularly those engaged with logic and set theory.

An Introduction

Finitely Supported Mathematics

Gheorghe Paun

This book constitutes the refereed proceedings of the 12th International Symposium on Fundamentals of Computation Theory, FCT '99, held in Iasi, Romania in August/September 1999. The 42 revised full papers presented together with four invited papers were carefully selected from a total of 102 submissions. Among the topics addressed are abstract data types, algorithms and data structures, automata and formal languages, categorical and topological approaches, complexity, computational geometry, concurrency, cryptology, distributed computing, logics in computer science, process algebras, symbolic computation, molecular computing, quantum computing, etc.

12th International Symposium, FCT'99 Iasi, Romania, August 30 - September 3, 1999 Proceedings

Fundamentals of Computation Theory

This book presents a set theoretical development for the foundations of the theory of atomic and finitely supported structures. It analyzes whether a classical result can be adequately reformulated by replacing a 'non-atomic structure' with an 'atomic, finitely supported structure’. It also presents many specific properties, such as finiteness, cardinality, connectivity, fixed point, order and uniformity, of finitely supported atomic structures that do not have non-atomic correspondents. In the framework of finitely supported sets, the authors analyze the consistency of various forms of choice and related results. They introduce and study the notion of 'cardinality' by presenting various order and arithmetic properties. Finitely supported partially ordered sets, chain complete sets, lattices and Galois connections are studied, and new fixed point, calculability and approximation properties are presented. In this framework, the authors study the finitely supported L-fuzzy subsets of a finitely supported set and the finitely supported fuzzy subgroups of a finitely supported group. Several pairwise non-equivalent definitions for the notion of 'infinity' (Dedekind infinity, Mostowski infinity, Kuratowski infinity, Tarski infinity, ascending infinity) are introduced, compared and studied in the new framework. Relevant examples of sets that satisfy some forms of infinity while not satisfying others are provided. Uniformly supported sets are analyzed, and certain surprising properties are presented. Finally, some variations of the finite support requirement are discussed. The book will be of value to researchers in the foundations of set theory, algebra and logic.

A Set Theoretical Viewpoint

Foundations of Finitely Supported Structures

Bogdan Aman

The design of formal calculi in which fundamental concepts underlying interactive systems can be described and studied has been a central theme of theoretical computer science in recent decades, while membrane computing, a rule-based formalism inspired by biological cells, is a more recent field that belongs to the general area of natural computing. This is the first book to establish a link between these two research directions while treating mobility as the central topic. In the first chapter the authors offer a formal description of mobility in process calculi, noting the entities that move: links (π-calculus), ambients (ambient calculi) and branes (brane calculi). In the second chapter they study mobility in the framework of natural computing. The authors define several systems of mobile membranes in which the movement inside a spatial structure is provided by rules inspired by endocytosis and exocytosis. They study their computational power in comparison with the classical notion of Turing computability and their efficiency in algorithmically solving hard problems in polynomial time. The final chapter deals with encodings, establishing links between process calculi and membrane computing so that researchers can share techniques between these fields. The book is suitable for computer scientists working in concurrency and in biologically inspired formalisms, and also for mathematically inclined scientists interested in formalizing moving agents and biological phenomena. The text is supported with examples and exercises, so it can also be used for courses on these topics.

Gabriel Ciobanu

About

Books

Join the club