Advances in Automata and Formal Language Theory

The field of automata and formal language theory is witnessing significant developments, with a focus on exploring the dynamics of bounded-degree automata networks, introducing new methods for generalized planning, and improving the efficiency of pattern matching algorithms. Researchers are also investigating the properties of circular automata, Kleene algebra, and relational pattern languages. Notably, the extension of the L* algorithm to learn symbolic automata over rational numbers and the introduction of the CORGI algorithm for efficient pattern matching are expected to have a substantial impact on the field.

Some noteworthy papers include: The paper on Active Learning of Symbolic Automata Over Rational Numbers, which extends the L* algorithm to learn symbolic automata over rational numbers, making it applicable to new settings like real RGX and time series. The CORGI paper, which introduces a new matching algorithm that offers quadratic time and space guarantees for finding single satisficing matches, outperforming existing RETE-based approaches.

Sources

On the Dynamics of Bounded-Degree Automata Networks

Kleene Algebra

Satisficing and Optimal Generalised Planning via Goal Regression (Extended Version)

Positive Characteristic Sets for Relational Pattern Languages

Active Learning of Symbolic Automata Over Rational Numbers

Atomic Gliders and CA as Language Generators (Extended Version)

Subgraph Isomorphism: Prolog vs. Conventional

CORGI: Efficient Pattern Matching With Quadratic Guarantees

Simplicity and irreducibility in circular automata

Built with on top of