The research area is currently experiencing significant advancements in the understanding and application of automata theory, logic, and computational complexity. A notable trend is the exploration of polynomial growth properties in tree automata and transducers, alongside the development of new logics and frameworks for efficient string querying and document spanners. Researchers are also delving into the expressive power and computational complexity of various logics, including extensions of Propositional Dynamic Logic and the unary-negation fragment of first-order logic. Additionally, there is a growing interest in the complexity of games and puzzles, as well as the development of new methods to prevent undesired behaviors in AI systems through reinforcement learning. The field is also seeing progress in the characterization of nonuniform deterministic finite automata over finite algebraic structures and the study of history-deterministic parity automata, with implications for reactive synthesis and algorithmic properties.

Noteworthy Papers

• The structure of polynomial growth for tree automata/transducers and MSO set queries: Introduces a method to decide the growth of ambiguity in tree automata and generalizes Bojańczyk's dimension minimization theorem.
• FC-Datalog as a Framework for Efficient String Querying: Proposes FC-Datalog fragments for optimizing core spanners, showcasing a tailored fragment for deterministic regex simulation.
• A Common Ancestor of PDL, Conjunctive Queries, and Unary Negation First-order: Introduces UCPDL+, a logic that strictly contains several known logics and queries, with decidable satisfiability and model checking problems.
• Nonuniform Deterministic Finite Automata over finite algebraic structures: Presents a full characterization of groups for which identity checking has a probabilistic polynomial-time algorithm.
• Complexity of Jelly-No and Hanano games with various constraints: Settles the complexity of Jelly-No with an unbounded number of colours and explores constraints on board size and colours.
• History-Deterministic Parity Automata: Games, Complexity, and the 2-Token Theorem: Proves the 2-token theorem for parity automata, improving the complexity of checking history-determinism.
• MONA: Myopic Optimization with Non-myopic Approval Can Mitigate Multi-step Reward Hacking: Introduces MONA, a method to prevent multi-step reward hacking in AI systems.
• On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version): Explores the data complexity of answering linear monadic datalog queries with LTL operators, showing undecidability results under certain complexity assumptions.