Pith Number

pith:Z7G6OGXM

pith:2026:Z7G6OGXMI3JLN3NL5J7HJ5JVP3

not attested not anchored not stored refs resolved

On the Size Complexity and Decidability of First-Order Progression

Daxin Liu, Jens Classen

First-order progression for local-effect, normal, and acyclic actions grows only polynomially under reasonable assumptions.

arxiv:2605.12691 v1 · 2026-05-12 · cs.AI

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{Z7G6OGXMI3JLN3NL5J7HJ5JVP3}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

under reasonable assumptions, first-order progression for these action classes grows only polynomially. Moreover, we show that when the KB belongs to decidable fragments such as two-variable first-order logic or universal theories with constants, the progression remains within the same fragment, ensuring decidability and practical applicability.

C2weakest assumption

The unspecified 'reasonable assumptions' on the knowledge base and action effects that enable the polynomial size bound; these restrictions to local-effect, normal, or acyclic actions are load-bearing but their precise scope is not detailed in the abstract.

C3one line summary

First-order progression for local-effect, normal, and acyclic actions is polynomial-sized and preserves decidable fragments such as two-variable logic.

References

24 extracted · 24 resolved · 0 Pith anchors

[1] Untersuchungen ¨uber das Eliminationsproblem der mathematischen Logik 1935

[2] [Arenaset al., 2018 ] Marcelo Arenas, Jorge A. Baier, Juan S. Navarro, and Sebastian Sardi ˜na. On the progres- sion of situation calculus universal theories with constants. In Michael Thielscher, Fra 2018

[3] Zum Entscheidungsproblem der mathematis- chen Logik.Mathematische Annalen, 99:342–372, 1928

[4] On the undecidability of the situation calculus extended with description logic ontologies 2015

[5] Corr ˆea and Giuseppe De Giacomo 2024

Receipt and verification

First computed	2026-05-18T03:09:49.830041Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

cfcde71aec46d2b6edabea7e74f5357ec4b5b5926e859c9fdc6e337d26207270

Aliases

arxiv: 2605.12691 · arxiv_version: 2605.12691v1 · doi: 10.48550/arxiv.2605.12691 · pith_short_12: Z7G6OGXMI3JL · pith_short_16: Z7G6OGXMI3JLN3NL · pith_short_8: Z7G6OGXM

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/Z7G6OGXMI3JLN3NL5J7HJ5JVP3 \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: cfcde71aec46d2b6edabea7e74f5357ec4b5b5926e859c9fdc6e337d26207270

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "5204805c12d40215d15d9aa817df4ea7cb25a6acc441a26e2549360e3fff29f8",
    "cross_cats_sorted": [],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "primary_cat": "cs.AI",
    "submitted_at": "2026-05-12T19:40:45Z",
    "title_canon_sha256": "44bf5b0e779d424a10e7d58b9aab718f346e90ea7528eb11d5328900743e1938"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.12691",
    "kind": "arxiv",
    "version": 1
  }
}