The convergence cost of non-monotone iteration: a linear certificate, an exponential critical point

In the revision theory of Gupta and Belnap a finite theory of self-referential sentences induces a non-monotone operator whose orbits are iterated from arbitrary hypotheses. Hsiung isolated the stage at which periodic behaviour becomes unavoidable, the critical point, and recorded the two bounds in the literature: the pigeonhole bound 2^(n) for finite concurrent theories, and, by construction, entry stages of order 2^(n-1) with n sentences. Neither is a maximum, and no condition on a theory is known to yield a rate. In the dependency-skeleton framework we settle both. First, one structural condition --- closure of the evaluation operator, checkable in polynomial time and assuming neither monotonicity nor acyclicity --- forces every orbit to converge with critical point at most n, the number of sentences; inside this class the exponential regime collapses to a linear one, and the bound is attained. Second, the general bound is exact: for every n there is a skeleton with a unique fixed point in which every orbit converges and the critical point is exactly 2^(n)-1. The pigeonhole bound is thus the answer, and it is reached without paradox: attaining it costs dependence width, not paradoxicality. Third, that cost is not what buys exponentiality: under out-degree 2 the construction has no room to run --- at n=3 the maximum falls to 6<7 --- yet a companion construction still settles in 2^((n+1)/2) rounds, so width sets the exponent's constant, not its presence; the exact maximum there is open.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-12
DOI
https://doi.org/10.5281/zenodo.24152080
Primary Topic
Logic, Reasoning, and Knowledge
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

The convergence cost of non-monotone iteration: a linear certificate, an exponential critical point

Rongjun Feng
Zenodo (CERN European Organization for Nuclear Research)
Logic, Reasoning, and Knowledge
preprint

The convergence cost of non-monotone iteration: a linear certificate, an exponential critical point

Rongjun Feng
preprint en

Abstract

In the revision theory of Gupta and Belnap a finite theory of self-referential sentences induces a non-monotone operator whose orbits are iterated from arbitrary hypotheses. Hsiung isolated the stage at which periodic behaviour becomes unavoidable, the critical point, and recorded the two bounds in the literature: the pigeonhole bound 2^(n) for finite concurrent theories, and, by construction, entry stages of order 2^(n-1) with n sentences. Neither is a maximum, and no condition on a theory is known to yield a rate. In the dependency-skeleton framework we settle both. First, one structural condition --- closure of the evaluation operator, checkable in polynomial time and assuming neither monotonicity nor acyclicity --- forces every orbit to converge with critical point at most n, the number of sentences; inside this class the exponential regime collapses to a linear one, and the bound is attained. Second, the general bound is exact: for every n there is a skeleton with a unique fixed point in which every orbit converges and the critical point is exactly 2^(n)-1. The pigeonhole bound is thus the answer, and it is reached without paradox: attaining it costs dependence width, not paradoxicality. Third, that cost is not what buys exponentiality: under out-degree 2 the construction has no room to run --- at n=3 the maximum falls to 6<7 --- yet a companion construction still settles in 2^((n+1)/2) rounds, so width sets the exponent's constant, not its presence; the exact maximum there is open.

Zenodo (CERN European Organization for Nuclear Research)
Logic, Reasoning, and Knowledge
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon