Idefix-Free Languages and Their Application in External Contextual Grammars

Marvin Ködding, Bianca Truthe · 2026

Read Idefix-Free Languages and Their Application in External Contextual Grammars by Marvin Ködding, Bianca Truthe (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26682.txt.

Description

Marvin Ködding and Bianca Truthe continue a study of contextual grammars and the families that control them. A contextual grammar builds sentences by adding word pairs around a starting core. A a selection set decides which cores may grow at each step. This work examines selection languages that are idefix-free, meaning no word contains another as an inner part, prefix, or suffix.

The authors compare these new families against many known families below the regular level. Subregular means simpler than fully regular languages. The comparisons cover finite, definite, commutative, circular, and other classic types. They then compare the rankings that external contextual grammars generate under each selection type. New families slot into the existing rankings, extending them. The results refine knowledge of how grammar power depends on the selector's simplicity.

Catalog record

CREATORMarvin Ködding, Bianca Truthe
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.26682

Browse the full library · About the Tower of Babel