Automata are of paramount importance in a wide range of fields. They are indispensable tools for text processing (regular expressions and finite automata) and parsing (grammars and pushdown automata). Automata can be used in different ways, as (1) acceptors, defining languages of accepted words, or (2) transformers, transforming words. Both aspects have been studied extensively for automata on finite words, but for infinite words the transformational aspect has hardly received attention. This proposal aims to fill this gap. In this proposal, we study automata on infinite words or streams. Finite automata accepting streams form the basis of software and hardware verification via model checking. Streams defined by finite automata, known as automatic sequences, play an important role in number theory. So there is a large body of research on finite automata for accepting and defining streams. Surprisingly, the transformational aspect of automata has hardly been studied when it comes to streams. Automata transforming streams are known as finite state transducers. Transducers are applied in speech and image processing, signal processing, to program verification, intrusion and malware detection. Although finite state transducers are a very simple and elegant form of automata, hardly anything is known about their power in transforming streams. The central objective of this proposal is the study of the capabilities and the limitations of finite automata for transforming streams.

The goal of this project is to develop software to help mathematicians write correct proofs. We will focus on number theory, a branch of mathematics dedicated primarily to the study of the integers, and collaborate with Dutch mathematicians to ensure the software is usable and works well with computer algebra systems.

Ever since their discovery lambda calculus (LC), combinatory logic (CL) and term rewriting systems (TRSs) have been instrumental in developments both in foundational areas and in applied directions. It all started with definability of arithmetic in lambda calculus. Thereby, LC turned out to be the vessel for the very notion of computability. The same turned out to hold for CL: both LC and CL are Turing-complete. Thus they seem to be the final universal systems. But in fact they are not. While they are complete with respect to what can be done, they are not complete with respect to how it can be done. They are extensionally complete, but not intensionally. They have the inherent constraint of being sequential in the nature of their processing. By contrast, general rewriting systems, which are based on pattern recognition, can define such parallel operators without effort. So we are confronted with the question what TRSs can LC and CL define? And how can we distinguish whether some rules can or cannot be realized in LC? And if two functions, given by their rewrite rules, are not definable, is one maybe more undefinable than the other? Are there degrees of undefinability? Could it help to join some undefinable rule sets to LC and CL, reaching a calculus that is also intensionally complete? Sequentiality versus parallelism has been studied in depth, but up to now mainly in a semantical sense, and not focusing on direct definability, where the rewrite relation itself is respected, rather than merely equality in some model.

-

Many fundamental computational tasks are performed on a graph, which is a mathematical abstraction of interactions in a network. In many applications the input graph is dynamic, i.e. it undergoes changes over time, and the output must be efficiently adjusted after each update. This project focuses on developing efficient dynamic graph algorithms for: (i) Maintaining data structures that return good estimates to shortest path distances between elements in the network. (ii) Partitioning the graph into clusters such that more similar elements are clustered together, where similarity is modelled by distances between elements.