Tootfinder

Which Word Orders Facilitate Length Generalization in LMs? An Investigation with GCG-Based Artificial Languages
Nadine El-Naggar, Tatsuki Kuribayashi, Ted Briscoe
https://arxiv.org/abs/2510.12722

Which Word Orders Facilitate Length Generalization in LMs? An Investigation with GCG-Based Artificial Languages
Whether language models (LMs) have inductive biases that favor typologically frequent grammatical properties over rare, implausible ones has been investigated, typically using artificial languages (ALs) (White and Cotterell, 2021; Kuribayashi et al., 2024). In this paper, we extend these works from two perspectives. First, we extend their context-free AL formalization by adopting Generalized Categorial Grammar (GCG) (Wood, 2014), which allows ALs to cover attested but previously overlooked cons…

On the Smallest Size of Internal Collage Systems
Soichiro Migita, Kyotaro Uehata, Tomohiro I
https://arxiv.org/abs/2509.11602 https://arxiv.org/pdf/2509.11…

On the Smallest Size of Internal Collage Systems
A Straight-Line Program (SLP) for a stirng $T$ is a context-free grammar in Chomsky normal form that derives $T$ only, which can be seen as a compressed form of $T$. Kida et al.\ introduced collage systems [Theor. Comput. Sci., 2003] to generalize SLPs by adding repetition rules and truncation rules. The smallest size $c(T)$ of collage systems for $T$ has gained attention to see how these generalized rules improve the compression ability of SLPs. Navarro et al. [IEEE Trans. Inf. Theory, 2021] s…

Black-box Context-free Grammar Inference for Readable & Natural Grammars
Mohammad Rifat Arefin, Shanto Rahman, Christoph Csallner
https://arxiv.org/abs/2509.26616 https://…

Black-box Context-free Grammar Inference for Readable & Natural Grammars
Black-box context-free grammar inference is crucial for program analysis, reverse engineering, and security, yet existing tools such as Arvada, TreeVada, and Kedavra struggle with scalability, readability, and accuracy on large, complex languages. We present NatGI, a novel LLM-guided grammar inference framework that extends TreeVada's parse tree recovery with three key innovations: bracket-guided bubble exploration, LLM- driven bubble generation and non-terminal labeling, and hierarchical delta…

A First Context-Free Grammar Applied to Nawatl Corpora Augmentation
Juan-Jos\'e Guzm\'an-Landa, Juan-Manuel Torres-Moreno, Miguel Figueroa-Saavedra, Ligia Quintana-Torres, Martha-Lorena Avenda\~no-Garrido, Graham Ranger
https://arxiv.org/abs/2510.04945

A First Context-Free Grammar Applied to Nawatl Corpora Augmentation
In this article we introduce a context-free grammar (CFG) for the Nawatl language. Nawatl (or Nahuatl) is an Amerindian language of the $π$-language type, i.e. a language with few digital resources, in which the corpora available for machine learning are virtually non-existent. The objective here is to generate a significant number of grammatically correct artificial sentences, in order to increase the corpora available for language model training. We want to show that a grammar enables us sig…

Reasoning Core: A Scalable RL Environment for LLM Symbolic Reasoning
Valentin Lacombe, Valentin Quesnel, Damien Sileo
https://arxiv.org/abs/2509.18083 https://

Reasoning Core: A Scalable RL Environment for LLM Symbolic Reasoning
We introduce Reasoning Core, a new scalable environment for Reinforcement Learning with Verifiable Rewards (RLVR), designed to advance foundational symbolic reasoning in Large Language Models (LLMs). Unlike existing benchmarks that focus on games or isolated puzzles, Reasoning Core procedurally generates problems across core formal domains, including PDDL planning, first-order logic, context-free grammar parsing, causal reasoning, and system equation solving. The environment is built on key des…