Automata Transforming Streams

Summary

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.

Details

Project number

VI.Vidi.192.004

Main applicant

Dr. J. Endrullis

Affiliated with

Vrije Universiteit Amsterdam, Faculteit der B├Ętawetenschappen (Faculty of Science), Afdeling Informatica (Computer Science)

Duration

01/09/2019 to 01/09/2024