The Kleene Meets Church project

Compiling Nondeterministic Transducers to Deterministic Streaming Transducers

Bjørn Bugge Grathwohl, Fritz Henglein, Ulrik Terp Rasmussen, Kristoffer Aalund Søholm, Sebastian Paaske Tørholm

DIKU, University of Copenhagen

What is Kleenex?

Kleenex is a programming language for stream processing of data in a regular domain. Programs consist of ambiguous grammars with embedded semantic actions, and all ambiguities are compiled away before run-time via a novel translation to determinstic streaming string transducers. The compiled programs have linear worst-case running time and sustained high throughput in the 1Gbps range.