Invited speakers

In 2017, the concept of Wheeler graphs was introduced. In these graphs, a total order on the alphabet induces an order among the nodes, which is then propagated forward by traversing pairs of edges with the same label.

Automata whose transition graphs are Wheeler graphs are known as Wheeler automata, where the states are ordered according to the alphabet order. These automata support efficient data structures for path queries and pattern matching on their languages; furthermore, they enable innovative compression techniques.

The regular languages accepted by Wheeler automata are called Wheeler languages. These form a subclass of star-free languages and exhibit several interesting properties from a language-theoretic perspective.

In this talk, we will present some of the main known properties and theoretical challenges on Wheeler automata and Wheeler languages highlighting their structural features and theoretical significance. We will also present our latest results on the closure properties of Wheeler languages, with a particular focus on closure under complementation.

Grammatical inference involves the learning of formal grammars from data, and inductive inference involves the learning of grammars from positive examples of words that are generated.

In this talk, we will present inductive inference of different types of Lindenmayer systems (L-systems). L-systems are particularly useful for creating simulations of plants and other processes with inherent parallelism. We mostly analyze the problem of being given one or more sequences of strings initially generated by an (unknown) L-system and attempting to infer an L-system that indeed can initially generate those sequences.

This includes different restrictions on L-systems such as deterministic, nondeterministic, tabled, non-tabled, erasing, non-erasing, context-free, context-sensitive, or parametric. We will survey older results on decidability of inference, and newer results on complexity.

Computational complexity will go hand-in-hand with descriptional complexity as we will strive to inductively infer L-systems with the smallest number of rewriting rules and/or the smallest number of tables. Computational complexity will also vary depending upon whether certain parameters of the L-system are taken to be fixed or not, leading to fixed-parameter tractable algorithms.

We also discuss more experimental results with implementations of inductive inference. Finally, we describe preliminary work on learning and matching L-systems to images.

There are many interesting open problems and future directions that remain in this area, which will be discussed.

Reversible computing has applications in debugging, robotics, simulation and biochemical modelling. Many such applications involve concurrency, which requires causal-consistent reversibility, where one can undo any action provided that its consequences, if any, are undone first.

There is an axiomatic theory for causal-consistent reversible computation, allowing one to prove many fundamental properties from a small set of easily verifiable axioms. One can study concurrency, causal dependence and conflict relations within the theory, however, only qualitatively.

In this ongoing work we complement the theory with a quantitative analysis, describing the computational cost of computing the relevant relations. We follow an axiomatic approach, so that it matches the generality of the qualitative part. We apply this new approach to CCSK with guarded recursion and reversible Erlang.

The technological and societal challenges of our time are increasingly demanding computational models and methods that surpass the limitations of Turing machines and are novel both in their architecture and operation. 

Natural computing attempts to address this challenge, among other things,  by drawing ideas from nature to develop computational models and providing novel computational tools to describe natural processes.

In this talk,  we discuss the descriptional complexity of P systems,  also known as membrane systems, and compare it with the descriptional complexity of some classical computational models in formal language theory and automata theory. We also attempt to formulate conditions for an appropriate definition of the notions and metrics of descriptional complexity for describing similar natural systems and processes. 

P systems, also known as membrane systems, are well-known parallel and distributed computational models that mimic the structure and function of living cells, tissues, and higher organizations such as groups of bacteria. Over the years, the theory and applications of membrane systems have become a recognized and vibrant scientific field, the field of membrane computing.