Pith Number

pith:MGTUWLE6

pith:2026:MGTUWLE65SIVEFGLTDSVQPUZYM

not attested not anchored not stored refs pending

Learning Tree Automata with Term Rewriting

Jakub Kopystia\'nski, Jan Otop

Supplying a term rewriting system allows the learning algorithm to deduce answers to some queries and thereby reduce the total number required to identify a tree automaton.

arxiv:2605.07710 v2 · 2026-05-08 · cs.FL

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

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{MGTUWLE65SIVEFGLTDSVQPUZYM}

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

We present an extension of the Angluin-style learning algorithm for tree automata that incorporates deductive inference. The learning algorithm is provided with a term rewriting system that specifies properties of the target tree language. This term rewriting system is used to infer answers to some queries, which reduces the query complexity of the learning algorithm.

C2weakest assumption

The supplied term rewriting system is assumed to be sound, complete, and consistent with the target language so that all deductive inferences drawn from it are correct and do not miss relevant equivalences.

C3one line summary

Extending tree automaton learning with term rewriting systems enables deductive answers to some queries and reduces query complexity for languages with specified properties.

Formal links

2 machine-checked theorem links

Receipt and verification

First computed	2026-05-25T02:02:16.415300Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

61a74b2c9eec915214cb98e5583e99c33c766c8fa56ded709f409fb73b92e780

Aliases

arxiv: 2605.07710 · arxiv_version: 2605.07710v2 · doi: 10.48550/arxiv.2605.07710 · pith_short_12: MGTUWLE65SIV · pith_short_16: MGTUWLE65SIVEFGL · pith_short_8: MGTUWLE6

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/MGTUWLE65SIVEFGLTDSVQPUZYM \
  | 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: 61a74b2c9eec915214cb98e5583e99c33c766c8fa56ded709f409fb73b92e780

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "f669f41b64e6400ad6a52a442cd50d8ecc8a30b3c8a86be4908c3a33a905c2c4",
    "cross_cats_sorted": [],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.FL",
    "submitted_at": "2026-05-08T13:15:59Z",
    "title_canon_sha256": "c8f8f9dc0f83c07e3d45b065c9f170a73458c17e30234d2fdfc1b5d6b503dcc9"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.07710",
    "kind": "arxiv",
    "version": 2
  }
}