Source-linked AI summary
On smallest synchronizing terms over constant alphabets
Luisa Herrmann, Richard Mörbitz
TL;DR
The paper studies how large the reset threshold of synchronizing DTA can be when the alphabet has only two symbols, addressing the gap between quadratic lower bounds and exponential upper bounds. It develops a two-symbol construction based on unary and binary transitions, obtaining subexponential lower bounds equivalent to Landau's function. The construction narrows the gap but cannot improve the resulting bound further because its unary iteration is already maximized by Landau's function.
Problem
For DTA over constant-sized alphabets, the known reset-threshold lower bound is quadratic while the upper bound is exponential, unlike prior exponential lower bounds requiring growing alphabets.
Method
The paper constructs DTA using only a unary symbol w and a binary symbol f, abstracting synchronization as nested compositions of their transition functions.
Results
The construction gives a subexponential lower bound with growth equivalent to Landau's function and also yields polynomial lower bounds of every degree greater than 1.
Takeaways & Limitations
Two symbols suffice to raise constant-alphabet DTA reset thresholds from quadratic to subexponential and substantially narrow the gap toward the exponential upper bound.
Takeaways & Limitations
The construction cannot improve its bound further because it iterates a unary function as long as Landau's function permits, while the binary function acts only as a guard.
Abstract
from arXiv · showhide
We show a subexponential lower bound on the reset threshold of synchronizing deterministic finite tree automata (DTA) over alphabets of just two symbols. This significantly improves the previous one, which was quadratic in the number of states. Our result also narrows the gap towards the lower bound for DTA over alphabets that grow linearly with the number of states, as well as the best known upper bound, both of which are currently exponential.
1 Introduction
Synchronization asks whether an automaton can map every starting state to one fixed state, but tree automata introduce branching and leave a large constant-alphabet gap between quadratic and exponential reset-threshold bounds. The paper addresses this gap with a two-symbol construction yielding stronger lower bounds.
- DFA synchronization: A synchronizing word maps every state of a DFA to one fixed state.The shortest such word defines the DFA's reset threshold.
- Tree automata: DTA generalize DFA by recognizing branching trees, with reset threshold defined as the height of the smallest synchronizing term.The tree counterpart of a synchronizing word is a synchronizing term.
- Open gap: For constant-sized DTA alphabets, known bounds leave a gap between a quadratic lower bound and an exponential upper bound.Exponential lower bounds had previously required alphabets growing with the number of states.
- Contribution: The paper constructs two-symbol DTA families with lower bounds growing as Ω(n^d) for every d ≥ 2 and with subexponential growth equivalent to Landau's function.The construction uses only two alphabet symbols and improves existing reset-threshold lower bounds.
2 Basic Notions
The paper develops the formal vocabulary for ranked alphabets, trees, contexts, composition, and Landau's function. These definitions support treating branching tree structures and nested function compositions within one framework.
- Composition: Function composition is defined by applying one function after another, with repeated unary composition denoted by powers.The framework also permits composed higher-arity functions and tracks their tree-like syntactic height.
- Ranked alphabets and trees: A ranked alphabet assigns each symbol a rank indicating its number of successor nodes.Rank-0 symbols are leaves, while higher-rank symbols create branching.
- Ranked alphabets and trees: Trees generalize strings by allowing each symbol to have a fixed number of successors determined by its rank.A tree's height is the longest path from its root to a leaf or variable.
- Contexts: A context is a tree with no repeated variables whose variables occur in left-to-right order, and a full context contains no leaves.Contexts provide open tree structures into which other trees can be plugged.
- Number theory: Landau's function g(n) is the largest least common multiple obtained from positive parts whose sum is at most n.The paper uses partitions witnessing g(n) to parameterize its later construction.
3 Tree Automata and Synchronization
Deterministic tree automata process ranked trees bottom-up, using transition functions whose arities match symbol ranks. Synchronization is characterized through reachable state sets and equivalent nested compositions of unary and binary transitions.
- Tree automata: A bottom-up DTA assigns each ranked symbol a deterministic transition function whose input arity equals that symbol's rank.Unlike a DFA, it needs no initial state because nullary leaf transitions are constants.
- Reachability: Extending transitions to sets of states determines all states reachable from arbitrary inputs at the tree's variable positions.For a variable-free tree, determinism makes the reachable set a singleton.
- Synchronization: A full context is synchronizing when its reachable state set has cardinality one.A DTA is synchronizing if such a context exists, and its reset threshold is the minimum synchronizing height.
- Composition viewpoint: Synchronization can equivalently be studied as finding the shallowest composition of transition functions that maps all states to one singleton.The paper abstracts this problem to unary δw and binary δf functions before returning to DTA.
4 Construction of δf and δw
The construction partitions [n] into blocks, defines δw as cyclic motion within blocks, and defines δf to delay productive synchronization until a designated set is reached. Starting from [n], the first reachable singleton appears after exactly LCM + 1 nested applications, under the stated corner-case exclusions.
- Definitions: The construction partitions [n] into k blocks of lengths ℓ1, …, ℓk and a residual interval, then defines δw and δf over these states.The alphabet uses w and f to represent the two transition functions.
- Behavior of δw: The LCM − 1 application of δw maps A0 to F, while the next application returns to the cycle.Every block length divides LCM, so LCM successive applications produce a cycle and one fewer application yields F.
- Behavior of δw: δw cyclically shifts elements within each block, preserving exactly one element from every block under repeated applications to A0.The entire set [n] is fixed by δw, while the constructed set A0 evolves through blockwise shifts.
- Behavior of δf: δf maps F to {1}, but maps every other set reachable from A0 through δw back to A0, preventing earlier synchronization.Thus δf cannot abbreviate the sequence before F is reached.
- Synchronization depth: The reachable-set characterization shows that the smallest h for which a singleton is reachable is exactly LCM + 1.No reachable set through depth LCM is a singleton; F is reached at depth LCM and δf then yields {1}.
- Scope: The delayed-switching technique relies on the binary function δf and cannot be reproduced by unary DFA transition functions.The paper contrasts this with the at-most n^2 synchronization bound for two synchronizable DFA states.
5 Lower bounds on smallest synchronizing terms
The construction converts chosen integers into DTAs whose smallest synchronizing-term height is one more than their least common multiple, yielding arbitrary-degree polynomial and subexponential lower bounds over two-symbol alphabets.
- General construction: The construction uses state set [n] and alphabet {w, f}, with synchronization at height h equivalent to Reachh containing a singleton.The transition function is defined through δw and δf.
- General construction: lcm{ℓ1, . . . , ℓk}+1 is the smallest synchronizing-term height guaranteed by the general DTA construction.The construction requires ℓ1 + ··· + ℓk ≤ n, k ≥ 2, and at least one ℓi ≥ 2.
- Polynomial lower bounds: For every fixed degree d ≥ 2, selecting d large primes yields DTA families with polynomial reset thresholds of degree d.The prime-selection strategy uses the d largest primes up to ⌊n/d⌋ and applies the least-common-multiple construction.
- Polynomial lower bounds: The polynomial lower bound underestimates the threshold for some initial n, but the construction still establishes arbitrary polynomial degrees.A more elaborate choice of pairwise coprime numbers could cover more initial values, while the presented strategy remains conceptually simple.
- Subexponential lower bound: Choosing ℓ1, . . . , ℓk to maximize their least common multiple under total sum at most n yields a subexponential reset threshold.The resulting least common multiple grows as e(1+o(1))·n·ln n.
- Subexponential lower bound: For every n ≥ 5, a DTA with n states has smallest synchronizing-term height g(n)+1, where g is Landau’s function.The construction chooses integers whose sum is at most n and whose least common multiple equals g(n).
- Subexponential lower bound: The proof strategy can be implemented by restricting the search to powers of pairwise distinct primes and optimizing their partition with dynamic programming.This optimization maximizes the product of selected prime powers under the state budget.
6 Outlook
The paper improves the constant-alphabet lower bound from quadratic to subexponential and also supplies weaker polynomial families of every degree greater than one. Its construction cannot improve the bound further because its unary iteration already reaches Landau’s-function maximum.
- Outlook: The lower bound for DTA over constant-sized alphabets improves from quadratic to subexponential.This narrows the gap toward the still-exponential upper bound of 2^n−n−1.
- Outlook: The technique also constructs DTA families with polynomial thresholds for every degree greater than 1.These polynomial families are weaker than the paper’s subexponential construction.
- Outlook: The construction cannot improve its subexponential bound further because it iterates a unary function as long as Landau’s function permits.The binary function acts only as a guard in this construction.