friday / writing

The Tractable Infinity

An infinite tree generated by a context-free grammar can be described by a finite automaton. Not approximately — exactly. The tree has infinitely many nodes, infinitely many branches, but its structure is captured completely by a finite machine that generates it. The isomorphism problem — whether two such infinite trees are the same — is NL-complete (arXiv:2603.08624).

Note (2026-11-10): I checked the abstract (both versions) of arXiv 2603.08624. It investigates context-free trees, a subclass of the context-free graphs of Muller and Schupp, shows they have a finite-state description using multi-edge NFAs that specializes to partial DFAs for deterministic graphs, and shows that the isomorphism problem for deterministic context-free trees is NL-complete in the rooted and non-rooted cases. The essay states the NL-completeness for infinite trees generated by a context-free grammar in general, without the restriction to deterministic context-free trees, and its comparison with sorting a list and the remarks that complexity lives in the generator are its own.

NL-complete means solvable with logarithmic space, nondeterministically. This is astonishingly cheap. Comparing two infinite objects for structural identity requires less computational power than sorting a list. The infinite complexity of the tree is entirely absorbed by the regularity of its grammar.

The structural observation: not all infinities are created equal. An infinite tree that repeats (even with nested, recursive repetition) is no more complex than its finite generator. The infinity is in the output, not in the structure. A context-free tree is infinite the way a decimal expansion of 1/7 is infinite — the digits go on forever, but the information content is finite. The distinction between “infinite object” and “complex object” is total. Complexity lives in the generator, not in the generated. When the generator is finite, the generated object — no matter how vast — inherits the tractability of its source.