pith. sign in

arxiv: 2606.26682 · v1 · pith:GSZGBWFTnew · submitted 2026-06-25 · 💻 cs.FL

Idefix-Free Languages and Their Application in External Contextual Grammars

Marvin K\"odding (PH Heidelberg) , Bianca Truthe (Universit\"at Giessen) This is my paper

Pith reviewed 2026-06-26 02:03 UTC · model grok-4.3

classification 💻 cs.FL
keywords contextual grammarsidefix-free languagessubregular languagesexternal contextual grammarslanguage hierarchiesprefix-free languagessuffix-free languagesinfix-free languages
0
0 comments X

The pith

External contextual grammars that select derivations with idefix-free languages generate new families that extend known hierarchies of subregular languages.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies infix-free, prefix-free, and suffix-free languages, grouped as idefix-free languages, and uses them as selection mechanisms inside external contextual grammars. It places the resulting language families beside previously studied subregular classes such as finite, monoidal, nilpotent, definite, and star languages. The central move is to locate these new families inside the existing hierarchy diagrams for external contextual grammars and thereby add fresh entries. A reader cares because the comparison shows how a single restriction on the selector changes the generative capacity in a way that is neither trivial nor already covered by earlier restrictions. The work therefore refines the map of how limited regular selectors control the power of contextual grammars.

Core claim

By investigating infix-, prefix-, and suffix-free languages as selection languages for external contextual grammars and comparing the families they generate to the families obtained from finite, monoidal, nilpotent, combinational, definite, ordered, non-counting, power-separating, commutative, circular, union-free, star, and comet languages, the paper obtains new language families that can be inserted into the existing hierarchies, thereby extending those hierarchies.

What carries the argument

idefix-free selection languages inside external contextual grammars, which restrict the context-selection step while still producing families that sit at new positions relative to other subregular selectors.

If this is right

  • The idefix-free families sit strictly between some of the listed subregular families and the full regular languages in the hierarchy.
  • New inclusion or incomparability relations appear among the families generated by external contextual grammars.
  • The generative power of external contextual grammars is shown to be sensitive to the precise free-language restriction placed on the selector.
  • The hierarchies become finer, with additional layers between the previously known levels.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same idefix-free selectors could be tested inside internal contextual grammars to see whether the same extensions appear.
  • Decidability or complexity questions for membership in these new families might be settled by reduction to the corresponding questions for the selector languages.
  • The comparison technique used here could be applied to other named subregular classes not yet examined as selectors.

Load-bearing premise

The idefix-free families must be distinct from the already-listed subregular families and must occupy non-trivial new positions inside the hierarchy of external contextual grammars.

What would settle it

An explicit proof or counter-example showing that every language generated by an external contextual grammar with an idefix-free selector is already generated by one of the previously studied subregular selectors.

Figures

Figures reproduced from arXiv: 2606.26682 by Bianca Truthe (Universit\"at Giessen), Marvin K\"odding (PH Heidelberg).

Figure 1
Figure 1. Figure 1: Resulting hierarchy of subregular language families. [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Resulting hierarchy of language families by external contextual grammars with special selec [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
read the original abstract

In this paper, we continue the research on the power of contextual grammars with selection languages from subfamilies of the family of regular languages. We investigate infix-, prefix-, and suffix-free languages (referred to as idefix-free languages) and compare such language families to some other subregular families of languages (finite, monoidal, nilpotent, combinational, (symmetric) definite, ordered, non-counting, power-separating, commutative, circular, union-free, star, and comet languages). Further, we compare the families of the hierarchies obtained for external contextual grammars with the language families defined by these new types for the selection. In this way, we extend the existing hierarchies by new language families.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript continues research on contextual grammars using subregular selection languages by defining and studying infix-, prefix-, and suffix-free languages (collectively called idefix-free languages). It compares the resulting families to fourteen other subregular families (finite, monoidal, nilpotent, combinational, (symmetric) definite, ordered, non-counting, power-separating, commutative, circular, union-free, star, and comet languages) and then inserts the new families into the hierarchies of languages generated by external contextual grammars, claiming to extend those hierarchies.

Significance. If the comparisons establish that at least one idefix-free family is strictly incomparable to or properly contained in the previously studied subregular classes, thereby inserting new nodes into the external contextual grammar hierarchy, the result would add concrete new families to the known classification. The paper states that comparisons are performed, which, if backed by explicit separating examples, would constitute a non-trivial extension.

major comments (1)
  1. Abstract: the claim that the idefix-free families extend the existing hierarchies by producing new positions requires demonstration that the three new families are distinct from the fourteen listed subregular families in a non-trivial way (proper inclusion or incomparability). The abstract asserts that comparisons are performed, yet the load-bearing step is the provision of witness languages or counter-examples separating the new families; without these, the claimed extension could collapse onto already-known positions in the hierarchy.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed report and the opportunity to clarify the manuscript. We address the major comment point by point below.

read point-by-point responses

  1. Referee: [—] Abstract: the claim that the idefix-free families extend the existing hierarchies by producing new positions requires demonstration that the three new families are distinct from the fourteen listed subregular families in a non-trivial way (proper inclusion or incomparability). The abstract asserts that comparisons are performed, yet the load-bearing step is the provision of witness languages or counter-examples separating the new families; without these, the claimed extension could collapse onto already-known positions in the hierarchy.

    Authors: We agree that explicit separating examples are essential to substantiate the claimed extensions. Sections 3 and 4 of the manuscript contain the required comparisons: for each idefix-free family we provide concrete witness languages demonstrating both proper inclusions and incomparabilities with the fourteen listed subregular families (finite, monoidal, nilpotent, etc.). These witnesses are then used in Section 5 to insert the new families at distinct positions within the external contextual grammar hierarchies. The abstract's reference to performed comparisons is therefore supported by these explicit constructions. Should the referee consider the presentation of any particular witness insufficiently prominent, we can add a dedicated summary table in a revision. revision: no

Circularity Check

0 steps flagged

No circularity; standard family comparisons without self-referential reductions

full rationale

The paper extends hierarchies of external contextual grammars by comparing infix-, prefix-, and suffix-free (idefix-free) selection languages against fourteen listed subregular families. All steps rely on standard definitions from prior literature and explicit inclusion/incomparability arguments; no equations, fitted parameters renamed as predictions, or load-bearing self-citations appear in the provided text. The central claims rest on external definitions and (presumably) witness languages or proofs that are independent of the present work, rendering the derivation self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review limits visibility into assumptions; no free parameters or invented entities mentioned. Relies on standard definitions of regular language subfamilies and contextual grammar operations from prior work.

axioms (1)
  • standard math Standard definitions and closure properties of regular language subfamilies hold as background.
    Invoked implicitly when comparing families; common in formal language theory.

pith-pipeline@v0.9.1-grok · 5664 in / 1033 out tokens · 21601 ms · 2026-06-26T02:03:42.719003+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 17 canonical work pages

  1. [1]

    Theoretical Computer Science 410(35), pp

    Henning Bordihn, Markus Holzer & Martin Kutrib (2009): Determination of finite automata accepting sub- regular languages. Theoretical Computer Science 410(35), pp. 3209–3222, doi:10.1016/j.tcs.2009.05.019

    work page doi:10.1016/j.tcs.2009.05.019 2009

  2. [2]

    Brzozowski (1962): Regular expression techniques for sequential circuits

    Janusz A. Brzozowski (1962): Regular expression techniques for sequential circuits. Ph.D. thesis, Princeton University, Princeton, NJ, USA

    1962

  3. [3]

    Brzozowski (1967): Roots of star events

    Janusz A. Brzozowski (1967): Roots of star events . Journal of the ACM 14(3), pp. 466–477, doi:10.1109/SW AT.1966.21

    work page doi:10.1109/sw 1967

  4. [4]

    Brzozowski & Rina Cohen (1969): On decompositions of regular events

    Janusz A. Brzozowski & Rina Cohen (1969): On decompositions of regular events . Journal of the ACM 16(1), pp. 132–144, doi:10.1145/321495.321505. 70 Idefix-Free Languages and Their Application in External Contextual Grammars

    work page doi:10.1145/321495.321505 1969

  5. [5]

    Brzozowski, Galina Jirásková & Chenglong Zou (2014): Quotient complexity of closed languages

    Janusz A. Brzozowski, Galina Jirásková & Chenglong Zou (2014): Quotient complexity of closed languages. Theory of Computing Systems 54, pp. 277–292, doi:10.1007/s00224-013-9515-7

    work page doi:10.1007/s00224-013-9515-7 2014

  6. [6]

    Fundamenta Informaticae 64(1–4), pp

    Jürgen Dassow (2005): Contextual grammars with subregular choice . Fundamenta Informaticae 64(1–4), pp. 109–118

    2005

  7. [7]

    Analele Universitatii Bucuresti 62, pp

    Jürgen Dassow (2015): Contextual languages with strictly locally testable and star free selection languages. Analele Universitatii Bucuresti 62, pp. 25–36

    2015

  8. [8]

    Theoretical Computer Science 449, pp

    Jürgen Dassow, Florin Manea & Bianca Truthe (2012): On external contextual grammars with subregular selection languages. Theoretical Computer Science 449, pp. 64–73, doi:10.1016/j.tcs.2012.04.008

    work page doi:10.1016/j.tcs.2012.04.008 2012

  9. [9]

    Journal of Automata, Languages, and Combinatorics 17(2–4), pp

    Jürgen Dassow, Florin Manea & Bianca Truthe (2012): On Subregular Selection Languages in Inter- nal Contextual Grammars . Journal of Automata, Languages, and Combinatorics 17(2–4), pp. 145–164, doi:10.25596/jalc-2012-145

    work page doi:10.25596/jalc-2012-145 2012

  10. [10]

    RAIRO – Theoretical Informatics and Applications57, p

    Jürgen Dassow & Bianca Truthe (2023): Relations of contextual grammars with strictly locally testable selection languages. RAIRO – Theoretical Informatics and Applications57, p. #10, doi:10.1051/ita/2023012

    work page doi:10.1051/ita/2023012 2023

  11. [11]

    Academiai Kiado, Budapest

    Ference Gécseg & István Peák (1972): Algebraic Theory of Automata. Academiai Kiado, Budapest

    1972

  12. [12]

    Kou (1974): Multiple-entry finite automata

    Arthur Gill & Lawrence T. Kou (1974): Multiple-entry finite automata. Journal of Computer and System Sciences 9(1), pp. 1–19, doi:10.1016/S0022-0000(74)80034-6

    work page doi:10.1016/s0022-0000(74)80034-6 1974

  13. [13]

    Havel (1969): The theory of regular events II

    Ivan M. Havel (1969): The theory of regular events II. Kybernetika 5(6), pp. 520–544

    1969

  14. [14]

    Markus Holzer & Bianca Truthe (2015): On relations between some subregular language families. In Rudolf Freund, Markus Holzer, Nelma Moreira & Rogério Reis, editors: Seventh Workshop on Non-Classical Mod- els of Automata and Applications – NCMA 2015, Porto, Portugal, August 31 – September 1, 2015. Proceed- ings, books@ocg.at 318, Österreichische Computer ...

    2015

  15. [15]

    Sorin Istrail (1978): Gramatici contextuale cu selectiva regulata. Stud. Cerc. Mat 30, pp. 287–294

    1978

  16. [16]

    Marvin Ködding & Bianca Truthe (2024): Various Types of Comet Languages and their Application in Exter- nal Contextual Grammars. In Florin Manea & Giovanni Pighizzini, editors: Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2024), NCMA 2024, Göttingen, Germany, 12–13 August 2024, EPTCS 407, pp. 118–135, ...

    work page doi:10.4204/eptcs.407.9 2024

  17. [17]

    RAIRO – Theoretical Informatics and Applications

    Marvin Ködding & Bianca Truthe (submitted): Idefix-Closed Languages and Their Application in Contextual Grammars. RAIRO – Theoretical Informatics and Applications

  18. [18]

    Journal of Automata, Languages, and Combinatorics

    Marvin Ködding & Bianca Truthe (submitted): Various Types of Comet Languages and Their Application in Contextual Grammars. Journal of Automata, Languages, and Combinatorics

  19. [19]

    Manfred Kudlek (2004): On languages of cyclic words . In Natasha Jonoska, Gheorghe P ˘aun & Grzegorz Rozenberg, editors: Aspects of Molecular Computing, Essays Dedicated to Tom Head on the Occasion of His 70th Birthday, LNCS 2950, Springer-Verlag, pp. 278–288, doi:10.1007/978-3-540-24635-0_20

    work page doi:10.1007/978-3-540-24635-0_20 2004

  20. [20]

    Revue Roumaine de Mathématique Pures et Appliquées14, pp

    Solomon Marcus (1969): Contextual grammars. Revue Roumaine de Mathématique Pures et Appliquées14, pp. 1525–1534

    1969

  21. [21]

    MIT Press, Cambridge, USA

    Robert McNaughton & Seymour Papert (1971): Counter-Free Automata. MIT Press, Cambridge, USA

    1971

  22. [22]

    Benedek Nagy (2019): Union-freeness, deterministic union-freeness and union-complexity . In Michal Hospodár, Galina Jirásková & Stavros Konstantinidis, editors:Descriptional Complexity of Formal Systems, 21st IFIP WG 1.02 International Conference, DCFS 2019, Košice, Slovakia, July 17–19, 2019, Proceedings, Springer, Cham, pp. 46–56, doi:10.1007/978-3-030-...

    work page doi:10.1007/978-3-030-23247-4_3 2019

  23. [23]

    Viktor Olejár & Alexander Szabari (2025): Closure Properties of Subregular Languages Under Operations. Int. J. Found. Comput. Sci. 36(7), pp. 1063–1087, doi:10.1142/S0129054123450016

    work page doi:10.1142/s0129054123450016 2025

  24. [24]

    Journal of the ACM 12(3), pp

    Azaria Paz & Bezalel Peleg (1965): Ultimate-definite and symmetric-definite events and automata. Journal of the ACM 12(3), pp. 399–410, doi:10.1145/321281.321292

    work page doi:10.1145/321281.321292 1965

  25. [25]

    Perles, Michael O

    Micha A. Perles, Michael O. Rabin & Eli Shamir (1963): The theory of definite automata. IEEE Transactions of Electronic Computers 12, pp. 233–243, doi:10.1109/PGEC.1963.263534. M. Ködding & B. Truthe 71

    work page doi:10.1109/pgec.1963.263534 1963

  26. [26]

    Springer, doi:10.1007/978-3-642-59136-5

    Grzegorz Rozenberg & Arto Salomaa, editors (1997): Handbook of Formal Languages . Springer-Verlag, Berlin, doi:10.1007/978-3-642-59136-5

    work page doi:10.1007/978-3-642-59136-5 1997

  27. [27]

    Hon Min Book Co., Taichung, Taiwan

    Huei-Jan Shyr (1991): Free Monoids and Languages. Hon Min Book Co., Taichung, Taiwan

    1991

  28. [28]

    Tamkang Journal of Mathematics 5(1), pp

    Huei-Jan Shyr & Gabriel Thierrin (1974): Ordered automata and associated languages. Tamkang Journal of Mathematics 5(1), pp. 9–20

    1974

  29. [29]

    Mathematical Systems Theory 8(1), pp

    Huei-Jan Shyr & Gabriel Thierrin (1974): Power-separating regular languages. Mathematical Systems Theory 8(1), pp. 90–95, doi:10.1007/BF01761710

    work page doi:10.1007/bf01761710 1974

  30. [30]

    In Suna Bensch, Rudolf Freund & Friedrich Otto, editors: Sixth Workshop on Non-Classical Models for Automata and Applica- tions – NCMA 2014, Kassel, Germany, July 28–29, 2014

    Bianca Truthe (2014): A relation between definite and ordered finite automata . In Suna Bensch, Rudolf Freund & Friedrich Otto, editors: Sixth Workshop on Non-Classical Models for Automata and Applica- tions – NCMA 2014, Kassel, Germany, July 28–29, 2014. Proceedings , books@ocg.at 304, Österreichische Computer Gesellschaft, pp. 235–247

    2014

  31. [31]

    Technical Report, Justus-Liebig- Universität Giessen, Institut für Informatik, IFIG Research Report 1801

    Bianca Truthe (2018): Hierarchy of Subregular Language Families . Technical Report, Justus-Liebig- Universität Giessen, Institut für Informatik, IFIG Research Report 1801

    2018

  32. [32]

    Fundamenta Informaticae 180(1–2), pp

    Bianca Truthe (2021): Generative capacity of contextual grammars with subregular selection languages . Fundamenta Informaticae 180(1–2), pp. 123–150, doi:10.3233/FI-2021-2037

    work page doi:10.3233/fi-2021-2037 2021

  33. [33]

    Diplo- marbeit, Universität Rostock

    Barbara Wiedemann (1978): Vergleich der Leistungsfähigkeit endlicher determinierter Automaten . Diplo- marbeit, Universität Rostock

    1978