Language Inference with Multi-head Automata through Reinforcement Learning

2020-10-20 · Alper Şekerci, Özlem Salehi

The purpose of this paper is to use reinforcement learning to model learning agents which can recognize formal languages. Agents are modeled as simple multi-head automaton, a new model of finite automaton that uses multiple heads, and six different languages are formulated as reinforcement learning problems. Two different algorithms are used for optimization. First algorithm is Q-learning which trains gated recurrent units to learn optimal policies. The second one is genetic algorithm which searches for the optimal solution by using evolution inspired operations. The results show that genetic algorithm performs better than Q-learning algorithm in general but Q-learning algorithm finds solutions faster for regular languages.

📄 PDF Abstract BibTeX arXiv:2010.10141

Code (0)

등록된 구현이 없습니다.

Tasks

Q-Learningreinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Methods 이 논문이 사용한 방법론

Q-Learning Q-Learning is an off-policy temporal difference control algorithm: $$Q\left(S\_{t}, A\_{t}\right) \leftarrow Q\left(S\_{t}, A\_{t}\right) + \alpha\left[R_{t+1} +…

Pre$^3$: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation

2025-06-04 · Junyi Chen, Shihao Bai, Zaijun Wang, Siyu Wu 외

Extensive LLM applications demand efficient structured generations, particularly for LR(1) grammars, to produce outputs in specified formats (e.g., JSON). Existing methods primarily parse LR(1) grammars into a pushdown a…

Active learning of timed automata with unobservable resets

2020-07-03 · Léo Henry, Nicolas Markey, Thierry Jéron

Active learning of timed languages is concerned with the inference of timed automata from observed timed words. The agent can query for the membership of words in the target language, or propose a candidate model and ver…

Active Learning

Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata

2026-07-08 · Meihua Dang, Stefano Ermon arxiv

Constrained decoding is essential for serving LLMs, ensuring that generated outputs follow specific structures such as JSON schema-formatted function calls. Existing systems are designed for autoregressive models and ass…

Prediction of Infinite Words with Automata

2016-03-08 · Tim Smith

In the classic problem of sequence prediction, a predictor receives a sequence of values from an emitter and tries to guess the next value before it appears. The predictor masters the emitter if there is a point after wh…

Prediction

Watermarks for Language Models via Probabilistic Automata

2025-12-11 · Yangkun Wang, Jingbo Shang arxiv

A recent watermarking scheme for language models achieves distortion-free embedding and robustness to edit-distance attacks. However, it suffers from limited generation diversity and high detection overhead. In parallel,…

Computational Efficiency