形式语言与自动机理论：2025–2026 年度综述

An annual survey of the cs.FL arXiv category, covering research published from September 2025 – August 2026. Built on a close-reading set of 108 papers and organised into 40 chapters, it maps the year by the field's research sub-directions.

Book framework (share of the year's output):

• Reachability and Verification in Infinite-State Systems (17.3%) — This cluster focuses on reachability and verification problems for infinite-state systems such as vector addition systems with states (VASS) and counter machines, often with dimension and counter constraints.
• Temporal Logic, Model Checking, and Runtime Verification (17.3%) — This cluster addresses formal verification of temporal properties via model checking, runtime monitoring, and probabilistic or stochastic extensions for complex systems.
• Combinatorics on Words and Infinite Sequences (13.5%) — This cluster studies combinatorial properties of finite and infinite words, including automatic sequences, Fibonacci words, and complexity measures of word representations.
• Regular Languages, Expressions, and Omega-Regular Properties (13.5%) — This cluster investigates decision problems, expressivity, and counting or sampling for regular and omega-regular languages, including their algebraic and automata-theoretic characterizations.
• Formal Language Methods for Large Language Models and Natural Language (10.9%) — This cluster explores the intersection of formal language theory and natural language processing, particularly the role of automata and logic in understanding and verifying large language models.
• Finite Automata, Weighted Automata, and Quantitative Models (10.1%) — This cluster focuses on structural and quantitative aspects of finite automata, including weighted, deterministic, and quantum variants, with emphasis on complexity and expressiveness.
• Context-Free Grammars, Parsing, and Language Inclusion (8.0%) — This cluster addresses algorithmic and theoretical issues for context-free languages, including parsing efficiency, grammar transformations, and inclusion problems.
• Automata Learning and Reinforcement Learning with Formal Specifications (5.6%) — This cluster combines automata learning with reinforcement learning and active learning to synthesize or infer formal specifications from traces or environments.
• Cellular Automata, Group Actions, and Topological Dynamics (3.7%) — This cluster studies cellular automata from algebraic, categorical, and topological perspectives, focusing on decidability, transitivity, and universality properties.

Each sub-direction is covered across three chapters — how it framed its questions, the strength of its key findings, and its open debates and frontiers — so the reader gets a traceable picture of what this part of the field actually produced over the year.