CS Paper Radar

An Explicit Ordinal Bound for System T Dialogue Trees

MingKun Xiao, YiXuan Sun

cs.LO ·submitted 2026-09-17 13:28 UTC · v1

Abstract

Escardó's dialogue interpretation assigns to each closed term $t:(ι\toι)\toι$ of Gödel's System~T a well-founded, countably branching tree $D(t)$, where $ι$ is the natural-number type. We give a direct proof that its classical ordinal height is below $ε_0$. More precisely, we compute a natural number $K(t)\ge2$ from the type levels occurring in the source term and prove $h(D(t))<θ_{K(t)}$, where $θ_0=ω$ and $θ_{n+1}=ω^{θ_n}$. Our proof translates recursors into closed infinitary templates and eliminates $β$-redexes by a finite sequence of passes indexed by ordinary type level. The translation and every pass preserve the dialogue denotation exactly. An auxiliary rank $ρ$ satisfies an additive substitution bound; each pass sends rank $α$ to at most $2^α$. Combining these estimates with a computable initial bound $ω+m(t)$ and a dialogue-height bound $2^{ρ(N)}$ for closed ground normal forms $N$ yields the stated tower bound. A semantics-preserving translation transfers the result to Escardó's original combinatory interpretation. We formalise the proof in Agda over classical ordinals under explicit foundational assumptions.

Comment
19 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable

cs.FL cs.LO ·2026-10-29 ·Mingkun Xiao, Yixuan Sun
theory similarity 0.62
Abstract · 31 pages, 3 figures. Rocq artifact: https://doi.org/10.5281/zenodo.23734555

Higher-order recursion schemes (HORS) are finite, simply typed recursive programs that generate potentially infinite trees. Their monadic second-order model-checking problem is decidable. We prove that tree equivalence of deterministic HORS is undecidable and, more precisely, $Π^0_1$-complete under total computable many-one reductions. The lower bound holds for safe, productive schemes of order at most four over the fixed ranked alphabet $Σ_2=\{e:0,d:2\}$, consisting of one nullary and one binary symbol. Adapting the counter-guard witness of Boiret, Piorkowski, and Schmude, we generate all candidate executions of a two-counter machine by producing both continuations at every counter test. An integer weight is nonzero exactly on legal prefixes. Functions at fixed simple types represent the polynomial of growing degree. A shift recurrence updates them without storing a separate step counter, allowing the witness to be implemented by safe applicative HORS rules. At candidate halts, the intermediate schemes generate unary observation subtrees whose lengths encode the two natural-number components of the signed weight. Invalid candidates give matching observations; a legal halt produces a finite discrepancy. Fixed constructor contexts encode these intermediate trees over $Σ_2$. For the upper bound, a finite monotone semantics decides head convergence and supports an algorithm computing exact tree prefixes at any prescribed finite depth, including positions labelled $\bot$.

0.32

The Gentzen-style monadic translation of Gödel's System T revisited

cs.LO ·2026-10-04 ·Chuangjie Xu
theory similarity 0.58
Abstract · Extended version of "A Gentzen-Style Monadic Translation of Gödel's System T" (FSCD 2020), DOI: 10.4230/LIPIcs.FSCD.2020.25

We revisit the Gentzen-style monadic translation of Gödel's System T. The translation is parametrized by a nucleus, a monad-like structure that need not satisfy the monad laws. A fundamental theorem of logical relations provides a uniform correctness argument for its instances. By choosing suitable nuclei, we obtain majorants, moduli of pointwise and uniform continuity, internal dialogue trees, and functionals of general bar recursion, all represented by terms of T. The internal dialogue-tree application gives a simpler construction, with correctness established directly using Church-encoded terms. We also extend the translation and its fundamental theorem to sums and finite lists. Finally, we develop the Kuroda-style translation and its continuity instance, comparing the moduli obtained with those of the Gentzen-style translation.

0.20

A Width Hierarchy of Monotone Algebraic Branching Programs

cs.CC ·2026-11-04 ·Julian Dörfler, Alexander Rogovskyy
theory similarity 0.57
Abstract · 28 pages, submitted to STOC 2027

It is well known that $\mathsf{VF} = \mathsf{VBP}_{3}$ (Ben-Or-Cleve'92), i.e. the width of any constant-width algebraic branching program can be reduced to width $3$ with only a polynomial overhead to size. We prove that this is not the case for the monotone equivalents. In particular, we prove that there is an infinite hierarchy $\mathsf{mVBP}_{2} \subsetneq \mathsf{mVBP}_{3} \subsetneq \ldots$ by showing that $\mathrm{imm}_{k,n}$ requires width $w$ mABPs to have depth at least $\left(\frac{k}{w-1}\right)^{\frac{1}{2}\left\lfloor n^{\frac{1}{(w-2)}} \right\rfloor - 1}$ whenever $3 \leq w < k$. We prove this lower bound using support-based techniques. Since this lower bound is exact instead of asymptotic, it allows some width separations even for superconstant width. Moreover, it allows us to show that the expressive power of poly-sized monotone formulas of depth $2d$ is not reached by poly-sized mABPs of width $d-1$ but a width of $2d+1$ is sufficient. We contrast this to unbounded-depth monotone formulas, which are proven to be stronger than constant-width mABPs, but weaker than $\log$-width mABPs and incomparable for most widths in between. Finally, we generalize Snir's framework (Snir'80) for showing lower bounds on the number of leaves of monotone formulas to monotone formulas of multiplication depth $d^{\times}$, giving a lower bound of $n \cdot k^{d^{\times}(n^{\frac{1}{d^{\times}}} - 1)}$ for the iterated matrix multiplication polynomial and $\left(\left(e+o(1)\right) \ln^{\circ(d^{\times}-1)}(n)\right)^n$ for the permanent.

0.32

Adjacency Labeling Schemes of Size $\log n+O(\log\log^* n)$ for Graphs of Bounded Treewidth

cs.DS cs.DM ·2026-11-02 ·Noy Rotbart
similarity 0.56
Abstract · 23 pages, 9 figures

Gavoille and Labourel (ESA 2007) gave an adjacency labeling scheme of size $\log n+O(k\log\log n)$ for graphs of treewidth at most $k$, and asked whether $\log n+O(k)$ bits suffice. We give a labeling scheme of size $\log n+O(\log\log^* n)$ for every fixed $k$, the first improvement of the second-order term for any $k\ge 2$. Equivalently, there is an induced-universal graph with $n(\log^* n)^{O_k(1)}$ vertices for this family. We work with laminar families of intervals, in which a vertex finds each earlier neighbor as the owner of an interval of a given nesting depth around it. As long as every subtree occupies consecutive positions, the nesting depth must be logarithmic, and $\log\log n$ bits per neighbor follow. We give up contiguity. Heavy subtrees are moved out, which brings the depth down to $O(\log^* n)$; the intervals broken by the moves are repaired with $2^{O(k^3)}$ additional intervals per vertex; and the bits needed to find these intervals are paid for by the moved subtrees.

0.30

Step Recursion: Resource Profiles and Descent Quotients

cs.CC cs.LO ·2026-08-23 ·Kirill Osipov
similarity 0.56
Abstract · Companion to arXiv:2608.04871

We develop a resource representation for step recursion in which mutable-state width and recursion descent are explicit and independent parameters. A width bound $u$ controls the size of the encoded machine state, while an effective descent $ρ$ determines the available recursion depth $δ_ρ(u)$. For generalized-inverse descents, we derive the depth directly from generator growth and characterize the increasing sequences that can occur as generator orbits. We then connect this depth--width geometry to standard finite-branching computation. Every deterministic bounded-state dynamics is realizable by a single ordinary bounded step recursion over a fixed finite numerical basis. Using deterministic, existential, universal, or alternating aggregation on the same local dynamics yields the corresponding machine semantics. After closure under the width reparameterizations needed to absorb fixed local cost, the resulting language classes are exactly the machine time--space classes on profiles $(δ_ρ(u),u)$. Finally, profile domination quotients effective descents by admissible width reparameterization. Some depth curves collapse, yet polynomial widths support an explicit infinite strict hierarchy between the canonical polynomial- and exponential-depth profiles. Thus descent remains a nonredundant resource coordinate after polynomial width reparameterization; standard complexity classes are calibration points.

0.32

Jump Closure and Limit Uniformization in the Ideal Completion of the Turing Degrees

cs.LO math.LO ·2026-08-26 ·Miara Sung
similarity 0.54
Abstract

The Turing jump has no fixed point on the Turing degrees: $\mathbf a <_T \mathbf a'$ for every degree $\mathbf a$. After passing to the ideal completion, however, a natural fixed-point phenomenon appears. We study the Scott-continuous lifting $Γ:\operatorname{Idl}(\mathbf D_T)\to\operatorname{Idl}(\mathbf D_T)$, given by $Γ(I)=\downarrow\{\mathbf a':\mathbf a\in I\}$. Starting from the computable degree, Kleene iteration reaches its first fixed point at stage $ω$, namely the Turing ideal of arithmetical degrees; more generally, above $\mathbf a$ the least fixed point is the ideal of degrees arithmetical in $\mathbf a$. To pass beyond this fixed point, we introduce a limit-uniformization operator. Although the ideal of finite jumps contains every $\mathbf 0^{(n)}$, it does not contain the uniform limit oracle $\mathbf 0^{(ω)}=°_T\!\left(\bigoplus_{n < ω}0^{(n)}\right)$. The uniformization operator adjoins this oracle only when all finite jump degrees are present. It is monotone but not Scott-continuous. Composing jump closure with one such gate yields closure ordinal $ω\cdot 2$; gates at $ω,2ω,3ω,\ldots$ yield closure ordinal $ω^2$. Thus non-uniform closure under relativized halting problems is Scott-continuous and reaches fixed ideals, while uniform coding of an entire prior hierarchy is infinitary, discontinuous, and reopens diagonalization. This gives a domain-theoretic semantics for the successor/limit distinction in transfinite Turing-jump hierarchies and links failures of Scott continuity with closure ordinals.

0.25

A Tight Second-Order Lower Bound for Routing Labels in Trees

cs.DS ·2026-09-28 ·Hanqing Li
theory similarity 0.54
Abstract · 6 pages, no figures

In the designer-port routing-labeling problem, every vertex of a rooted tree receives a binary label and the child edges receive distinct port numbers. Given only the labels of a source and a destination, a decoder must return the first port on their path. Gawrychowski, Janczewski, and Lopuszanski gave labels of length $\log_2 n+O((\log_2\log_2 n)^2)$, whereas the previous lower bound was $\log_2 n+Ω(\log_2\log_2 n)$. We prove that every scheme for all $n$-vertex trees needs a label of length $\log_2 n+Ω((\log_2\log_2 n)^2)$ for every sufficiently large $n$. The result allows arbitrary port assignments and imposes no computational restriction on either the encoder or the decoder. Thus the second-order term in the optimal worst-case label length is determined up to constant factors.

0.20

A Uniform Algorithm for Strict NP on Bounded-Treedepth Graphs

cs.DS cs.CC ·2026-10-05 ·Thomas Depian, Robert Ganian, Jakob Greilhuber, Marlene Gründel, Simon Wietheger
similarity 0.54
Abstract

A classical well-quasi-ordering result guarantees the existence of non-uniform linear-time algorithms for all problems in Strict NP on relational structures of bounded treedepth; however, this provides neither a procedure for constructing these algorithms nor computable bounds on their parameter dependence. We turn this existential result into a uniform algorithmic metatheorem. Given a Strict NP sentence $\varphi$ and a relational structure $\mathcal{R}$, our algorithm decides whether $\mathcal{R}\models\varphi$ in time $f(|\varphi|, td(\mathcal{R})) \cdot |\mathcal{R}|$ for a computable function $f$, where the treedepth of $\mathcal{R}$ is measured on the Gaifman graph. The algorithm also constructs witness relations, with the polynomial exponent depending on their arity, and provides a unified framework for settling hereditary graph problems parameterized by treedepth. We also present several applications - among others, our result resolves open questions on the fixed-parameter tractability of computing the stack number, queue number, track number and twin-width parameterized by treedepth.

0.29