Advances in Automata Learning and Neuro-Symbolic Reasoning

The field of automata learning and neuro-symbolic reasoning is moving towards more efficient and scalable methods for learning and reasoning about complex systems. Recent developments have focused on improving the performance of automata learning algorithms, such as passive automata learning and active automata learning with stochastic delays. Additionally, there is a growing interest in neuro-symbolic architectures that can learn to solve discrete reasoning and optimization problems from natural inputs. These architectures have shown promising results in learning constraints and objectives for NP-hard reasoning problems. Furthermore, research has also explored the use of regular constraint propagation for solving string constraints, which has demonstrated effectiveness in both theoretical and experimental evaluations. Overall, the field is advancing towards more efficient and powerful methods for learning and reasoning about complex systems, with potential applications in a wide range of areas, including natural language processing, computer vision, and decision-making under uncertainty. Noteworthy papers in this area include those on passive automata learning of visibly deterministic context-free grammars and efficient neuro-symbolic learning of constraints and objectives. The paper on passive automata learning of visibly deterministic context-free grammars presents a novel algorithm for learning deterministic context-free grammars from positive and negative samples. The paper on efficient neuro-symbolic learning of constraints and objectives introduces a differentiable neuro-symbolic architecture and a loss function dedicated to learning how to solve NP-hard reasoning problems from natural inputs.

Sources

Combined Approximations for Uniform Operational Consistent Query Answering

Prover-Adversary games for systems over (non-deterministic) branching programs

Synthesizing DSLs for Few-Shot Learning

Disjunctions of Two Dependence Atoms

Passive Model Learning of Visibly Deterministic Context-free Grammars

Uppaal Coshy: Automatic Synthesis of Compact Shields for Hybrid Systems

Automata Learning -- Expect Delays!

Constraints-Guided Diffusion Reasoner for Neuro-Symbolic Learning

Performance analysis for cone-preserving switched systems with constrained switching

Complexity in finitary argumentation (extended version)

On The Space Complexity of Partial Derivatives of Regular Expressions with Shuffle

Natural Language Satisfiability: Exploring the Problem Distribution and Evaluating Transformer-based Language Models

Certificates and Witnesses for Multi-objective {\omega}-regular Queries in Markov Decision Processes

Weighing Obese Timed Languages

The Computational Complexity of Satisfiability in State Space Models

Efficient Computation of Blackwell Optimal Policies using Rational Functions

Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms

Exact Persistent Stochastic Non-Interference

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations

Scaling Up Reachability Analysis for Rectangular Automata with Random Clocks

The Power of Regular Constraint Propagation (Technical Report)

Efficient Neuro-Symbolic Learning of Constraints and Objective

Built with on top of