ASPECTS OF COMPUTATION AND AUTOMATA THEORY WITH APPLICATIONS

This volume results from two programs that took place at the Institute for Mathematical Sciences at the National University of Singapore: Aspects of Computation — in Celebration of the Research Work of Professor Rod Downey (21 August to 15 September 2017) and Automata Theory and Applications: Games, Learning and Structures (20–24 September 2021).

The first program was dedicated to the research work of Rodney G. Downey, in celebration of his 60th birthday. The second program covered automata theory whereby researchers investigate the other end of computation, namely the computation with finite automata, and the intermediate level of languages in the Chomsky hierarchy (like context-free and context-sensitive languages).

This volume contains 17 contributions reflecting the current state-of-art in the fields of the two programs.

Contents:

• Generators of the CE Degrees and Strongly Meet Inaccesssible Degrees (Klaus Ambos-Spies, Decheng Ding and Peter Fejer)
• Cuts in the ML Degrees (Katherine Arthur, Noam Greenberg and Joseph S Miller)
• Cantor–Bendixson Ranks for Almost Prime Models (Nikolay Bazhenov and Margarita Marchuk)
• Isomorphism Types of Rogers Semilattices in the Analytical Hierarchy (Nikolay Bazhenov, Sergey Ospichev and Mars Yamaleev)
• Immunity, Diagonalization and the Complexity of Mass Problems (Achilles A Beros, Mushfeq Khan, Bjørn Kjos-Hanssen and André Nies)
• Computability and Categoricity of Weakly Homogeneous Boolean Algebras and p-Groups (Douglas Cenzer, Francis Adams and Keng Meng Ng)
• From Quasi-Dominions to Progress Measures (Massimo Benerecetti, Daniele Dell'Erba, Marco Faella and Fabio Mogavero)
• Effective Ultrapowers and Applications (Rumen D Dimitrov and Valentina Harizanov)
• FPT-Inspired Approximations (Henning Fernau)
• Disjoint NP-Pairs and Propositional Proof Systems (Christian Glaβer, Andrew Hughes, Alan L Selman and Nils Wisiol)
• How to Verify Computations with a Rational Network (Sanjay Jain, Prateek Saxena, Frank Stephan and Jason Teutsch)
• Punctual Degrees and Lattice Embeddings (Iskander Kalimullin, Alexander Melnikov and Maxim Zubkov)
• Maximal Automatic Complexity and Context-Free Languages (Bjørn Kjos-Hanssen)
• Roots of Polynomials in Fields of Generalized Power Series (Julia Knight, Karen Lange and Reed Solomon)
• A Scalable Verification Solution for Blockchains (Jason Teutsch and Christian Reitwieβner)
• Weak Muller Conditions Make Delay Games Hard (Sarah Winter and Martin Zimmermann)
• A Turing Machine like Model for Computation on Real Numbers (Yue Yang)

Readership: Advanced undergraduate students, graduate students and researchers interested in automata theory, computabillty theory, complexity theory and recursion theory.

Key Features:

• Comprehensive and original collection of cutting-edge topics on automata theory, computational complexity and recursion theory
• The contributors are expert researchers in these fields and both contribute new scientific results and ideas for future directions
• The articles are an interdisciplinary mix dealing with computations from the concrete level of the theory of finite automata through the theoretical limits explored in recursion theory and also cover the middle in between with excursions into game theory and parameterized complexity