Advances in Logical Foundations and Automata Theory

The field of logical foundations and automata theory is witnessing significant developments, with a focus on exploring new models and characterizations of computational systems. Researchers are actively investigating the connections between logic, automata, and machine learning, leading to a deeper understanding of the expressive power and limitations of various computing frameworks. Notably, the study of graded modal substitution calculus and its variants has led to new insights into the equivalence of classes of pointed Kripke models and the expressive power of computing models. Furthermore, the introduction of new automaton models, such as deterministic suffix-reading automata, has enabled more concise recognition of regular languages. The development of quantitative types for the Functional Machine Calculus has also provided a framework for guaranteeing termination and strong normalization in the presence of computational effects. Some noteworthy papers in this area include:

  • The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic, which establishes a unifying framework for understanding the logical expressiveness of GNNs.
  • Games for graded modal substitution calculus, which introduces semantic games to study the expressive power of GMSC and its variants.
  • Deterministic Suffix-reading Automata, which presents a new automaton model for recognizing regular languages more concisely.

Sources

Operator Spaces, Linear Logic and the Heisenberg-Schr\"odinger Duality of Quantum Theory

A class of distributed automata that contains the modal mu-fragment

Games for graded modal substitution calculus

The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic

Deterministic Suffix-reading Automata

Characterization and Decidability of FC-Definable Regular Languages

Quantitative Types for the Functional Machine Calculus

Deconstructing Subset Construction -- Reducing While Determinizing

Built with on top of