Matching works

7 works

math.CO — Combinatorics

An upper bound for the connective constant of the square lattice

Contributed by Tejasvi Singh Tomar

We prove that the connective constant μ\mu of the square lattice Z2\mathbb{Z}^2, the exponential growth rate of the number of nn-step self-avoiding walks, satisfies μ≤2.6586513\mu\le2.6586513. The previous best upper bound, μ≤2.662342426\mu\le2.662342426, is due to Couronné. Like the bounds of Pönitz and Tittmann and of Couronné, ours comes from a finite automaton that remembers a bounded part of the past of the walk. The new idea is to count bridges. Since they can all be preceded by the same infinite history, the automaton may treat as visited the unvisited cells that no infinite self-avoiding continuation can reach, and three tests on the current state and the next step recognize such cells. The bound is checked in exact integer arithmetic and proved in the Lean proof assistant.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23715896

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 15, 202610 pages
PDFView work

math.PR — Probability

Certified upper bounds for the Chvátal–Sankoff constant

Contributed by Tejasvi Singh Tomar

Let γ2\gamma_2 be the Chvátal–Sankoff constant, so that the expected length of a longest common subsequence of two independent uniformly random binary strings of length nn is γ2n+o(n)\gamma_2n+o(n). Lueker proved γ2≤0.826280\gamma_2\le0.826280 with a finite automaton that reads a pair of strings as a sequence of minimal match pairs and remembers the last hh symbols of each string, for h=8h=8. We carry out his method up to h=13h=13 and prove γ2≤0.821963\gamma_2\le0.821963. For h=13h=13 the certificate lists 165,695,219,469165{,}695{,}219{,}469 states of the automaton, reduced by a symmetry. The bound rests on an explicit positive vector for the weighted transition matrix of the automaton; a checker rebuilds every transition with its own code and verifies the required inequalities in exact integer arithmetic. We also give a complete proof that the automaton accepts the truncated canonical decomposition of every pair of strings, the property on which the method depends. The bound γ2≤0.821963\gamma_2\le0.821963 is also proved in the Lean 4 proof assistant, with a computation evaluated by compiled code, and the bounds γ2≤0.825101\gamma_2\le0.825101, γ2≤0.824120\gamma_2\le0.824120, γ2≤0.823290\gamma_2\le0.823290 and γ2≤0.822579\gamma_2\le0.822579 for h=9h=9, 1010, 1111 and 1212 by formal proofs that are checked entirely by the Lean kernel.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23610945

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 15, 202611 pages
PDFView work

cs.FL — Formal Languages and Automata Theory

A superlogarithmic lower bound for deterministic word separation

Contributed by Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer

Let S(n)S(n) be the maximum, over distinct binary words of length nn, of the least number of states in a complete deterministic finite automaton that accepts exactly one of them. We prove S(n)≥(1−o(1))log⁡nlog⁡log⁡nS(n)\geq(1-o(1))\log n\log\log n. The main step is a common word of length exp⁡(O(klog⁡k))\exp(O(\sqrt{k}\log k)) that, after suitable powering of the generators, reaches the sink components of every transformation pair on kk states and attains minimum rank on each sink. This transfers the balanced positive permutation identities of Xu and Regan to the full transformation monoid without changing their leading logarithmic length. The conclusion concerns deterministic automata; it makes no assertion about nondeterministic separators.

Primarily AI-generated textHuman understanding: all partsdeterministic automataidentitiestransformation monoidsword separation
Nov 12, 20267 pages
PDFView work

cs.FL — Formal Languages and Automata Theory

Nonstabilization of the Predictive Boolean Lookahead Hierarchy

Contributed by Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer

We study the hierarchy of languages generated by predictive Boolean LL(k)\mathrm{LL}(k) grammars. The model uses a deterministic recursive-descent table, strongly non-left-recursive rules, and at least one positive conjunct per rule. For every integer r≥1r\geq1, we construct a language over a fixed eight-letter alphabet that has an ordinary LL(r+r2r+2)\mathrm{LL}(r+r2^r+2) grammar and establish that it has no predictive Boolean LL(r)\mathrm{LL}(r) grammar. The construction asks for a specified token in a uniquely decodable word. The lower bound represents parsing on a long unary prefix by finitely many forward-moving endpoint streams and a finite Boolean recurrence. Random binary blocks followed by homogeneous blocks separate streams with a persistent timing error from streams having an exact finite-state potential. A bounded-lookahead argument hides a token-count change from each remaining stream. An encoding of the resulting independent queries is then shorter than their arbitrary binary payload. This gives nonstabilization under the stated predictive convention. The conclusion is for the stated parser model, including positive-conjunct and strong non-left-recursion requirements. Path-dependent tables satisfying these requirements give the same language families.

Primarily AI-generated textHuman understanding: all partsBoolean grammarslookahead hierarchypredictive parsing
Nov 12, 202614 pages
PDFView work

cs.FL — Formal Languages and Automata Theory

Sublinear-space recognition for Boolean grammars

Contributed by Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer

For every fixed Boolean grammar in the standard language family considered by Okhotin, we give a deterministic membership algorithm using OG(n2/3(log⁡(n+2))2/3)O_G(n^{2/3}(\log(n+2))^{2/3}) working space on an input of length nn. In particular, the whole family is contained in DSPACE⁡(n3/4)\operatorname{DSPACE}(n^{3/4}), answering Okhotin's Problem 4 affirmatively. The construction partitions substring endpoints into blocks of size bb. It represents the parsing recurrence by a constant-fan-in circuit with OG(b2)O_G(b^2)-bit values and dependency height O(n/b+1)O(n/b+1). Splits in the endpoint blocks are resolved locally, and an ordering of the remaining splits controls the height even when a split is highly unbalanced. Applying the Cook–Mertz tree-evaluation algorithm to the implicitly unfolded circuit gives the space bound.

Primarily AI-generated textHuman understanding: all partsBoolean grammarsparsingspace complexitytree evaluation
Nov 11, 20266 pages
PDFView work

cs.FL — Formal Languages and Automata Theory

Decomposable disjoint-union circuits for primitive words

Contributed by Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer

For every fixed finite alphabet AA with at least two letters, we construct smooth decomposable circuits representing the primitive words of each length nn. The gates are literals, Cartesian products on disjoint position sets, and disjoint unions on equal position sets. The total number of gates and wires is OA(n25ω(n))=n2+o(1)O_A(n^2 5^{\omega(n)})=n^{2+o(1)}, and the construction takes n2+o(1)n^{2+o(1)} bit operations. Prime periods are expressed as coordinate directions of independent rectangular grids. A recursion at the first nonconstant vertex computes the exact set of failed directions; sharing its continuations gives the size bound. This resolves the primitive-word instance of the circuit question posed by Amarilli, Monet, Raphael, and Salvati. It does not determine whether primitive words form a context-free or a poly-slicewise-unambiguous language. The same circuit bound holds for any union of exact power orders at a fixed length.

Author comments: First version. Addresses the complement-free primitive-word circuit question in STACS 2026, Section 6. The main circuit-size theorem has a locally compiled Lean proof; the running-time and optional exact-order claims are separate from that formal verification. Independent mathematical review and priority have not been established.

Primarily AI-generated textHuman understanding: all partsdecomposable circuitsdisjoint unionsformal verificationprimitive words
Nov 10, 20267 pages
PDFView work

math.GR — Group Theory

An Executable Stallings Recognizer for Finite Generating Lists in Lean

Contributed by Arthur, David Barros Hulak, Ruy J. G. B. de Queiroz

We explain a Lean 4 construction of a finite inverse automaton recognizing the subgroup of the rank-two free group generated by any finite list of signed words. The implementation builds a flower multigraph and computes the least equivalence relation compatible with deterministic labelled transitions by exhaustive finite search over Boolean relations. Canonical representatives realize the folded graph on the original finite state type. A coset-potential invariant proves that folding introduces no additional subgroup elements; preservation of the input loops proves the opposite inclusion. A separate reduction argument shows that traversal of the canonical reduced representative decides membership. We distinguish the registered theorem, its executable witness, and classical reasoning used only in the proof. The construction retains unused states and has no formalized complexity, core-trimming, subgroup-basis, intersection, or index algorithm. This is an expository account of a classical recognition theorem and a pinned formal artifact, with no claim of mathematical novelty or formalization priority.

Primarily AI-generated textHuman understanding: some partsLean 4MathlibStallings foldingfinite inverse automatafree groupssubgroup membership
Oct 01, 20268 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations