Comparing the expressiveness of transducers and simply-typed linear lambda-calculi

点击翻译按钮获取中文摘要

Comparing the expressiveness of different computation models and formalisms is an important theme in many fields of theoretical computer science including complexity theory, descriptive complexity and automata theory. The main aims of this project would be to carry out such comparisons across classes of functions naturally defined by automata, lambda-calculi and logical interpretations, using techniques coming from automata theory and the semantics of linear logic.In 1996, a striking connection between lambda-calculus and automata was uncovered: the simply-typed functions from strings to booleans using Church encodings recognize exactly the class of regular languages. This sort of connection was then refined and further exploited by specialists of linear logic and automata to tackle problems related to higher-order model checking and automata running over infinite data.Following this, there was an effort in recent years to systematically compare the expressive power of Church encodings in linear lambda-calculi and string-to-string transductions, unveiling some non-trivial connections including a characterization of regular transductions. The techniques involve a mix of semantic evaluation, analyses of the normal forms in the lambda-calculus and non-trivial automata-theoretic results. To get a flavor of both the aims and the methods employed, one may skim through the following:- abstract outlining the programme: https://cs-web.swan.ac.uk/~cpradic/smp-abstract.pdf- PhD thesis on that topic: https://nguyentito.eu/thesis.pdf This project would be a continuation of that effort. There are a number of concrete problems to tackle that can serve as a good introduction to working in that setting, including:- comparing the expressiveness of the non-commutative linear lambda-calculus and first-order transducers- designing minimalistic typed programming languages capturing what is achievable in the linear lambda-calculus with Church encodings in the spirit of Bojanczyk's work on polyregular functions, but for comparison-free polyregular functions- carrying out a similar comparison for transducers over infinite structures and functions lambda-definable using the Church encoding of coinductive datatypes- checking whether there is difference in expressiveness if we allow the full power of classical linear logic instead of the intuitionistic fragmentThis could be followed-up by investigations in more challenging problems in the same area or into broader concerns specific to one of the domains involved (such as investigations which involving defining well behaved-class of tree transductions or more specialized topics in linear logic such as weak exponentials or quantification over linear types).While having a background in either mathematical logic or theoretical computer science would be necessary, a successful applicant would certainly not be expected to be familiar with all the tools mentioned above before starting.