CS Paper Radar

Non-Terminal Complexity of Simple Semi-Conditional Grammars

Henning Fernau, Sanjay Jain, Linus Richter, Frank Stephan, Dan Turetsky

cs.FL math.LO ·submitted 2026-09-12 23:04 UTC · v1
theory

Abstract

We study the complexity of simple semi-conditional grammars (SSCGs) in terms of the number of their terminals and non-terminals. We show that SSCGs with three non-terminals can generate all RE languages; two non-terminals suffice for linear languages; and one suffices for unary regular languages. We also determine both upper bounds and fundamental limitations of SSCGs: while certain one-non-terminal SSCGs can generate non-context-free languages, every language generated by a one-non-terminal SSCG is in non-deterministic linear space. We also prove that there exists a regular language of alphabet size at least 3 which cannot be generated by any one-non-terminal SSCG. Finally, we prove that membership testing for SSCGs of two non-terminals is already NP-hard.

Comment
26 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Independent Languages and Witnesses of Dependence (Non-satisfaction)

cs.FL ·2026-08-25 ·Stavros Konstantinidis
published similarity 0.68
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

We consider the independent language property defined by the language equation φ(X)=\emptyset, where the expression φ involves the language variable X, constant languages, and standard regular operations including transductions, but not complementation. This property consists of all languages L satisfying φ(L)=\emptyset. Depending on the choice of the operations in φ, the equation defines a broad class of codes, including combinations of standard variable-length codes and error-detecting codes. We show that any φ-independence is a Jürgensen independence, we define what a witness of non-satisfaction of φ(X)=\emptyset is, for a language L, and we show how to compute a witness of non-satisfaction when L is regular. We also discuss the complexity of the problem, showing that the decision version of the problem is PSPACE-complete.

0.48

Type-logical grammars and formal languages

cs.CC cs.CLcs.FLcs.LO ·2026-11-09 ·Richard Moot
theory similarity 0.67
Abstract

We show that type-logical grammars with the standard rules for product, associativity, extraction and infixation have an NP-complete fixed recognition problem, adapting a construction for first-order linear logic from Pshenitsyn (2025), who already showed that grammars in first-order linear logic are closed under intersection and therefore not semilinear and not mildly context-sensitive. We strengthen these results and shown that grammars in first-order linear logic can simulate the quasi-linear grammars of Book \& Greibach (1970), the grammars recognised in non-deterministic linear time (NSPACE(n) or. NLIN). I argue that NLIN is an interesting class of formal languages as well, and a useful upper bound on the time complexity of formalisms used for natural language, just like LOGCFL is a useful upper bound on the space complexity. Taken together this means that first-order linear logic can be seen as the logic of non-deterministic linear-time string languages, graph languages and automata.

0.18

Formal Grammars and Generating Functions: From Algebraic Structure to Non-Algebraic and Non-Derivable Series

cs.FL ·2026-10-22 ·Zhijun Wang
theory similarity 0.64
Abstract

This paper investigates how the algebraic and analytic properties of ordinary length generating functions constrain the grammatical and computational complexity of formal languages. We review the Chomsky-Schutzenberger representation, DSV translations for unambiguous context-free grammars, and their stack-indexed extensions, distinguishing finite algebraic systems from more general constructions. Examples and a diagonal argument demonstrate that even a rational generating function need not determine a language's grammatical class. Our central computability result establishes that, for a recursively enumerable language, computability of its length-counting sequence is equivalent to decidability of membership. Consequently, if a recursively enumerable language has a D-finite length generating function over Q(z), it is decidable; equivalently, undecidable recursively enumerable languages cannot have D-finite length generating functions. We then examine coefficient growth and singularities through Pringsheim's theorem, the Polya-Carlson dichotomy, Hadamard gaps, and Siegel G-functions. The resulting picture is asymmetric: analytic properties provide useful one-way constraints on language computability, but length enumeration loses too much information to determine grammatical or computational complexity without additional assumptions.

0.12

Contributions to the hierarchy of probabilistic languages

cs.FL cs.CLmath.LOmath.PR ·2026-09-20 ·Lothar Sebastian Krapp, Remo Nitschke
similarity 0.62
Abstract

We reconsider the theory of probabilistic formal languages generated by n-gram models and by probabilistic context-free grammars (PCFGs). The expected hierarchy of probabilistic grammars is established by proving that every probabilistic language generated by an n-gram model is also generated by some PCFG, while some probabilistic languages generated by PCFGs cannot be generated by any $n$-gram model. We introduce the notion of fully connected PCFGs, namely PCFGs in Chomsky normal form where every production rule only involving non-terminals has non-zero probability. Our main result shows that any probabilistic language generated by an $n$-gram model differs from any probabilistic language generated by a fully connected PCFG. Therefore, the class of probabilistic languages generated by $n$-gram models is not a subset of the class generated by fully connected PCFGs.

0.46

Exact Algorithms and Complexity of the Smallest Grammar Problem

cs.DS ·2026-10-23 ·Xiangle Chen
theory similarity 0.62
Abstract · Revised version with a uniform alphabet-sensitive subexponential algorithm and quantitative transfers to SAT. Source package includes verifi…

The Smallest Grammar Problem (SGP) asks for a smallest straight-line grammar generating a given string, with size measured by the total right-hand-side length. For an input of length $n\ge2$ over at most $σ$ symbols, where $2\leσ\le n$, let $R=\log_σn$. We give a deterministic exact algorithm running in $n^{O(1)}2^{O(n\log\log n/(R\sqrt{\log n}))}$ time and polynomial space, with constants independent of $σ$. This gives time $2^{O(n\log\log n/(\log n)^{3/2})}$ for fixed alphabets and $2^{O(n\log\log n/\sqrt{\log n})}$ for arbitrary alphabets, up to polynomial factors. The algorithm combines pairwise disjoint representative occurrences of dictionary strings, a sparse interval certificate, and the Boolean tensor contraction theorem of OpenAI. It explicitly enforces dictionary membership, rule boundaries, and the grammar-size budget. Independently of that contraction theorem, disjoint representatives yield exact algorithms in $O^*(1.872258^n)$ time and $2^{O((n/R)\log(R+1))}$ time using $O(n)$ words of space. Anchor-based grammar projections establish binary NP-completeness and reductions with tunable alphabet size. We state their consequences as unconditional quantitative transfers from SGP algorithms to sparse SAT algorithms, and quantify the additional loss from sparsifying general formulas.

0.45

Undecidability of Reachability for Constraint Automata

cs.FL ·2026-10-11 ·Jakub Michaliszyn
theoryhot direction similarity 0.62
Abstract

We prove that reachability for constraint automata over finite binary words is undecidable. Eight registers suffice, with conjunctive guards using only equality, proper prefix, proper suffix, and infix incomparability, without word constants or concatenation. Finite-run nonemptiness, Buechi nonemptiness, and bounded Buechi nonemptiness are undecidable as consequences. For Boolean guards over equality, prefix, suffix, and prefix and suffix incomparability, Buechi nonemptiness is PSPACE-complete with arbitrarily many registers and word constants. The upper bound also allows positive infix atoms and yields PSPACE-completeness of prefix--suffix LTL satisfiability.

0.31

Rational Reductions and Regular Languages of Constant Circuit Complexity

cs.CC cs.FLcs.LO ·2026-09-16 ·Stefan Göller, Amaldev Manuel
theory similarity 0.61
Abstract

We study the circuit complexity of regular languages in terms of unbounded fan-in Boolean circuit families. We characterize the regular languages of constant circuit complexity in terms of the one-variable fragment of first-order logic with regular predicates, in terms of the pseudovariety of stamps $\mathbf{QEJ}_\mathbf{1}$, suitable word congruences and regular expressions. We analogously characterize the neutral letter regular languages of constant circuit complexity. Our lower bound result implies that the class of regular languages of sublogarithmic circuit complexity coincides with the one of constant circuit complexity. In addition we show that deciding whether a regular language, given as a nondeterministic finite automaton, has constant circuit complexity is $\mathbf{PSPACE}$-complete. We introduce a strong notion of reduction, called rational truth-table reduction, that is tailored towards algebraically defined classes of languages. We show that, for a class of functions we call mild, rational truth-table reductions preserve both upper and lower bounds on circuit complexity. We show that the class of regular languages, whose circuit complexity is bounded by a mild function, is in fact a length-multiplying variety of languages. Slightly extending the class of regular languages of constant circuit complexity, we analogously characterize the class of regular languages that are in the pseudovariety $\mathbf{QEACom}$. For these we derive logarithmic circuit complexity upper bounds.

0.26

On the equivalence between generating functions computed by memory transducers and enumerating functions produced by indexed grammars

cs.FL ·2026-09-04 ·Vincent Ghigo
theory similarity 0.61
Abstract

We consider the sequences of natural integers that can be computed by a deterministic transducer, with input in a structure A, output in N. and with memory the set of stacks of stacks of A. We show that these sequences are, exactly, the counting sequences of formal languages generated by unambiguous context-free indexed grammars (equivalently, the counting sequences of derivation trees of arbitrary context-free indexed grammars), with indexes in A. This general theorem applies, notably, to the set of natural integers endowed with the operation -1 and the non-zero predicate, showing that the polynomial recurrences count exactly the index-languages (where the parameter used for counting is the index itself).

0.25