betaFeedback

WorksComputer Science

Operator Precedence Tree Automata

Abstract

Operator-precedence tree automata (OPTA) separate the construction of a word's syntactic structure from its recognition: an operator-precedence (OP) matrix determines a canonical tree, which is evaluated by a finite bottom-up automaton with regular horizontal transition languages. OPTA define exactly the operator-precedence languages. For a fixed matrix and language, a tree-context congruence yields an effectively constructible canonical complete deterministic exact recognizer, minimal in the number of vertical states and unique up to isomorphism. For acyclic OP matrices, we characterize balanced non-counting by aperiodicity of the context transition monoid of the canonical minimal ranked tree recognizer. Combined with existing characterizations of OP languages, this gives an equivalence with first-order definability over OP words, definability in Precedence-Oriented Temporal Logic (POTL), and star-free operator-precedence expressions for acyclic matrices.

Introduction

Operator-precedence languages (OPLs) originated in Floyd’s work on deterministic parsing of programming languages [10]. Their defining feature is a finite matrix of precedence relations between terminal symbols, which determines how a word is decomposed into nested syntactic units. Beyond their original application, OPLs form a family of deterministic context-free languages, properly containing Input Driven or Visibly Pushdown languages [14, 1] and retaining many of the properties that make regular languages useful. These include Boolean and concatenation closure under compatible precedence assumptions [6], and automata-theoretic and logical characterizations [13, 16]. Their local parsability also supports the analysis of separate input fragments, providing a basis for parallel parsing [2, 8].

Tree automata offer another way of extending finite-state methods beyond words. They recognize explicitly structured objects by assigning states to tree nodes according to the states computed on their children. Their theory provides context equivalences, determinization and minimization constructions, and connections with grammars and logic [CDG+08]. For unranked trees, regular languages describe the admissible sequences of child states, allowing finite descriptions even when node arity is unbounded [5]. These features suggest a natural connection with operator precedence: the matrix supplies a tree structure that a finite tree automaton can subsequently evaluate.

This connection brings together three views of syntax. A grammar gives a generative description of a language and its derivations. A matrix-driven OP parser gives an operational description: for a fixed precedence matrix MM, it already acts as a recognizer of the compatible-word language L(M)L(M) and determines a canonical tree TM(w)T_M(w) for each accepted word. A tree automaton, in turn, takes a tree as input and decides whether that supplied structure belongs to its language. In an operator-precedence automaton (OPA), structural parsing and the finite-state control selecting a particular language are performed together. Making their respective roles explicit allows the structural component of OP parsing to be combined directly with the recognition mechanisms of tree automata.

We introduce operator-precedence tree automata (OPTA) to formalize this combination. An OPTA consists of an OPM and a finite tree recognizer whose horizontal transition languages are regular. The matrix determines the OP tree of the input word; the recognizer then evaluates that tree from the leaves to the root. Terminal leaves retain their letters, while all internal nodes carry the same structural label, so neither grammar nonterminals nor boundary annotations need to be supplied as part of the input tree. This separates the construction of the structure from the acceptance condition and makes it possible to study the same language both as a set of words and as a set of canonical trees.

The connection also exposes an essential difference between the two theories. Concatenation of OPLs is ordinary word concatenation, whereas the products underlying regular tree expressions are based on substitution at designated leaves [CDG+08]. Similarly, composition of one-hole tree contexts substitutes one context into another. These operations cannot be identified merely by passing from a word to its tree: the structure assigned to a concatenation uvuv need not preserve the separately constructed trees of uu and vv as subtrees. Consequently, transferring a statement about regular expressions or star-freeness requires attention to the operation on which the expression formalism is based.

This distinction matters especially for aperiodicity. A fundamental result on regular word languages is the fact that aperiodicity, first-order definability, and star-freeness are equivalent [15]. The corresponding notions for tree languages do not coincide in general: standard star-free tree expressions can define counting languages, and there are aperiodic regular tree languages that are not first-order definable [11]. For OPLs, on the other hand, an equivalence between non-counting, first-order definability, and star-free operator-precedence expressions has been established under the relevant matrix assumptions [17]. OPTA provide a setting in which these results can be related to the algebra of tree contexts while keeping the underlying logical vocabulary and expression operations explicit.

Our results develop this connection in both directions. First, we prove that OPTA recognize exactly the OPLs over a fixed OP alphabet. The equivalence holds for arbitrary conflict-free matrices, including matrices with cycles in the equal-precedence relation; regular horizontal languages account for the unbounded arities that may arise in this case.

Second, we apply the tree-context Myhill-Nerode construction to obtain a canonical minimal exact OPTA. Exactness requires recognition of precisely the canonical tree language TM(L)T_M(L), including rejection of trees outside the OP-tree universe. This convention yields an effectively constructible minimum in the number of vertical states, unique up to isomorphism, for every conflict-free matrix. We also show why specifying behavior only on valid OP trees need not yield a unique minimum. The horizontal representation can be minimized separately once the canonical vertical quotient has been fixed.

Third, for acyclic matrices, we characterize balanced non-counting by aperiodicity of the context transition monoid of the canonical minimal ranked tree recognizer. Combined with [17], this yields an equivalence with first-order definability over OP words and with star-free operator-precedence expressions. It also gives an effective test through the finite context monoid. By the first-order completeness of POTL [7], these conditions are also equivalent to definability in a temporal logic for OP words. Thus, for acyclic matrices, the canonical ranked OPTA presentation connects aperiodicity, first-order definability, star-free operator-precedence expressions, and temporal logic, extending the familiar correspondence for regular word languages to this structured setting.

The transfer is therefore two-way: tree-automata methods provide canonical minimization for OP languages, while the logical and algebraic theory of OPLs yields aperiodicity characterizations for their canonical tree encodings. In this setting, we recover a correspondence between aperiodicity, logic, and expressions that fails for unrestricted tree languages. Here the logical side uses word positions equipped with order, letter predicates, and the OP chain relation, and the expression side uses word concatenation and the OP fence operation.

A closely related contribution is the Myhill-Nerode characterization of OPLs established in [12]. Their syntactic congruence is defined on words over a fixed operator-precedence alphabet: it refines chain equivalence and tests indistinguishability under embeddings compatible with the chain structure. They prove that this congruence has finite index exactly for OPLs, and exploit it to develop antichain algorithms for language inclusion and universality.

Our approach provides a complementary perspective by applying the tree-context Myhill-Nerode construction to the exact tree language TM(L)T_M(L). The objects being compared are internal-rooted trees, and the tests are substitutions into arbitrary one-hole tree contexts, with membership in TM(L)T_M(L) fixing rejection of invalid OP trees. The resulting equivalence classes are the vertical states of a canonical complete deterministic exact OPTA, minimal among such recognizers and unique up to isomorphism. This minimality statement concerns exact tree recognition for a fixed matrix; it does not assert minimality among ordinary operator-precedence automata. Furthermore, for acyclic matrices, the ranked presentation provides a context transition monoid whose aperiodicity characterizes balanced non-counting. Thus, the tree representation connects canonical minimization with the algebraic analysis of non-counting OPLs. The paper is structured as follows. § 2 recalls the required background. § 3 introduces OPTA and proves their equivalence with OPLs. § 4 develops canonical exact recognition and minimality, and § 5 establishes the aperiodicity characterizations.

Background

We assume familiarity with finite state automata, regular languages, context-free grammars, and tree languages [18 CDG+08]. Throughout, Σ\Sigma is a finite nonempty alphabet, ε\varepsilon is the empty word, and Σ+=Σ∗∖{ε}\Sigma^{+} = \Sigma^{*} \setminus\{\varepsilon\}. We study languages of nonempty words; empty factors and auxiliary languages containing ε\varepsilon are nevertheless allowed. The symbol #\#, not in Σ\Sigma, delimits words, and Σ#=Σ∪{#}\Sigma_{\#} = \Sigma\cup\{\#\}.

Trees and tree automata

All trees are finite, rooted, and ordered. For a tree tt, we write root⁡(t)\operatorname{root}(t) for its root and Int⁡(t)\operatorname{Int}(t) for its set of internal nodes, that is, nodes having at least one child. Its yield is the word obtained by reading its leaf labels from left to right. A ranked alphabet Γ\Gamma assigns an arity to each symbol; TΓT_{\Gamma} denotes the trees in which every node has the arity prescribed by its label. In an unranked tree, the label does not determine the number of children.

A bottom-up tree automaton computes a state at a node from its label and the states computed at its children. In the ranked case, a deterministic complete automaton has, for each symbol ff of arity kk, a total transition function Δf:Qk→Q\Delta_f : Q^{k} \to Q; for k=0k = 0, this specifies a state for the leaf ff. A tree is accepted when its root state is final. In the unranked case, transitions can instead be specified by regular languages of child-state sequences: a transition H→fqH \xrightarrow{f} q, with H⊆Q∗H \subseteq Q^{*} regular, permits state qq at an ff-node precisely when its child-state word belongs to HH [5]. Tree languages recognized by these devices are called regular. Bottom-up nondeterministic automata can be determinized in both settings. A deterministic tree automaton is reduced if every state is the root state of some input tree; that tree need not be accepted [CDG+08, Section 1.1].

A tree context has one distinguished hole □\Box in place of a subtree. We write C[t]C[t] for substitution of tt into the hole, and C[D]C[D] for composition of contexts. Iteration is defined by C0=□C^{0} = \Box and Cn+1=C[Cn]C^{n+1} = C[C^{n}].

Precedence matrices and chains

We recall here some basic definitions from the theory of Operator-Precedence languages [10 LMPPl15, MPI18].

A conflict-free operator-precedence matrix (OPM) is a partial map

M:Σ#×Σ#→{⋖,≐,⋗}.M : \Sigma_{\#} \times\Sigma_{\#} \to\{\lessdot, \doteq, \gtrdot\}.

We write a⋖ba \lessdot b, a≐ba \doteq b, or a⋗ba \gtrdot b when M(a,b)M(a,b) has the corresponding value, read as yields, is equal in, or takes precedence, respectively. These relations need not have the usual properties of an order. We use the boundary convention

#⋖a,a⋗#(a∈Σ),#≐#.\# \lessdot a,\qquad a \gtrdot\#\quad(a \in\Sigma),\qquad\# \doteq\#.

The pair (Σ,M)(\Sigma,M) is an OP alphabet. Matrix inclusion is entrywise: M′⊆MM' \subseteq M means that every relation specified by M′M' is also specified by MM. The matrix is total if every terminal-pair entry is defined, and acyclic if the directed graph of ≐\doteq on Σ\Sigma has no cycle.

Chains describe the structure induced by MM independently of grammar nonterminals. A simple chain, written a0[a1⋯ak]ak+1a_0[a_1 \cdots a_k]a_{k+1}, has k≥1k \ge1, a1,…,ak∈Σa_1,\ldots,a_k \in\Sigma, a0,ak+1∈Σ#a_0,a_{k+1} \in\Sigma_{\#}, M(a0,ak+1)M(a_0,a_{k+1}) defined, and

a0⋖a1≐⋯≐ak⋗ak+1.a_0 \lessdot a_1 \doteq\cdots\doteq a_k \gtrdot a_{k+1}.

A composed chain has the form

a0[w0a1w1⋯akwk]ak+1,a_0[w_0a_1w_1\cdots a_kw_k]a_{k+1},

where a0[a1⋯ak]ak+1a_0[a_1\cdots a_k]a_{k+1} is a simple chain and, for each 0≤i≤k0 \le i \le k, either wi=εw_i=\varepsilon or ai[wi]ai+1a_i[w_i]a_{i+1} is recursively a chain. The symbols a0,ak+1a_0,a_{k+1} are its boundaries, the word between brackets is its body, and a1⋯aka_1\cdots a_k is its skeleton.

A word w∈Σ+w \in\Sigma^{+} is compatible with MM if #[w]#\#[w]\# is a chain. We denote the set of such words by L(M)L(M). Conflict-freeness makes their recursive chain decomposition unique. Replacing each chain by one internal node and retaining its skeleton terminals and nonempty subchains as ordered children gives the OP tree used below. A skeleton of length kk gives at most 2k+12k+1 children. If MM is acyclic, its skeletons have no repeated terminal, so k≤∣Σ∣k \le|\Sigma|; thus OP trees have arity at most 2∣Σ∣+12|\Sigma|+1. Cyclic matrices do not impose any arity bound.

Grammars and operator-precedence automata

We use grammars G=(Σ,VN,P,S)G=(\Sigma,V_N,P,S) with a finite nonterminal set VNV_N disjoint from Σ\Sigma, a finite production set PP, and a nonempty set of axioms S⊆VNS \subseteq V_N. Empty and renaming productions are excluded. A production is in operator form if its right-hand side has no adjacent nonterminals. For such grammars, put

LG(A)={a∈Σ∣A⇒∗Caα, C∈VN∪{ε}},L_G(A)=\{a\in\Sigma\mid A\Rightarrow^{*}Ca\alpha,\ C\in V_N\cup\{\varepsilon\}\},
RG(A)={a∈Σ∣A⇒∗αaC, C∈VN∪{ε}},R_G(A)=\{a\in\Sigma\mid A\Rightarrow^{*}\alpha aC,\ C\in V_N\cup\{\varepsilon\}\},

where α\alpha ranges over (Σ∪VN)∗(\Sigma\cup V_N)^*. The induced matrix OPM⁡(G)\operatorname{OPM}(G) collects the relations

a≐bif A→αaCbβ∈P,C∈VN∪{ε},a \doteq b\quad\text{if }A\to\alpha aCb\beta\in P,\quad C\in V_N\cup\{\varepsilon\},
a⋖bif A→αaBβ∈P,b∈LG(B),a \lessdot b\quad\text{if }A\to\alpha aB\beta\in P,\quad b\in L_G(B),
a⋗bif A→αBbβ∈P,a∈RG(B),a \gtrdot b\quad\text{if }A\to\alpha Bb\beta\in P,\quad a\in R_G(B),

together with the boundary relations for the terminal sets of the axioms and #≐#\# \doteq\#. An operator grammar is an operator-precedence grammar (OPG) when OPM⁡(G)\operatorname{OPM}(G) is conflict-free [16].

The extension to cyclic matrices uses cyclic OPGs (C-OPGs) [8]. Their right-hand sides are regular expressions built using concatenation and positive iteration, subject to operator form; alternative productions provide finite union. An occurrence of A→rA \to r chooses a word α∈L(r)\alpha\in L(r) as the child sequence of that production occurrence. The precedence relations are computed over these instantiated right-hand sides, and must remain conflict-free. This permits unbounded child sequences without introducing auxiliary nonterminal nodes.

An operator-precedence automaton (OPA) has a finite control set QQ, initial and final sets I,F⊆QI,F \subseteq Q, a matrix MM, and transition functions

δpush,δshift:Q×Σ→2Q,δpop:Q×Q→2Q.\delta_{\mathrm{push}},\delta_{\mathrm{shift}}: Q \times\Sigma\to2^{Q}, \qquad\delta_{\mathrm{pop}}: Q \times Q \to2^{Q}.

Stack entries are pairs [a,p]∈Σ×Q[a,p] \in\Sigma\times Q, above a bottom marker ⊥\perp whose terminal symbol is #\#. Let qq be the current state, aa the top terminal, and bb the next input symbol. The matrix determines the move:

  • If a⋖ba \mathrel{\lessdot} b, consume bb, push [b,q][b,q], and choose a state in δpush(q,b)\delta_{\mathrm{push}}(q,b).

  • If a≐ba \doteq b, consume bb, replace the top entry [a,p][a,p] by [b,p][b,p], and choose a state in δshift(q,b)\delta_{\mathrm{shift}}(q,b).

  • If a⋗ba \mathrel{\gtrdot} b, remove [a,p][a,p] and choose a state in δpop(q,p)\delta_{\mathrm{pop}}(q,p), without consuming bb.

Shift and pop require a nonbottom entry. Acceptance starts with stack ⊥\perp and a state in II, and ends with stack ⊥\perp, a state in FF, and only the final #\# unread. An undefined relation blocks the run. A support of a chain a[x]ba[x]b is the computation fragment that reads its body xx, with bb as the final lookahead, and returns to the underlying stack prefix after closing the chain.

We call languages accepted by OPAs operator-precedence languages (OPLs). OPAs and OPGs define the same languages over an acyclic matrix [13]. C-OPGs provide the corresponding grammatical characterization for arbitrary conflict-free matrices [8].

Logical and algebraic background

For w=a1⋯an∈L(M)w = a_1 \cdots a_n \in L(M), set a0=an+1=#a_0 = a_{n+1} = \#. The associated word structure has domain {0,…,n+1}\{0,\ldots,n+1\}, the linear order <<, letter predicates PaP_a for a∈Σ#a \in\Sigma_{\#}, and the chain relation

χ(i,j)⟺i<j and ai[ai+1⋯aj−1]aj is a chain.\chi(i,j) \Longleftrightarrow i < j \text{ and } a_i[a_{i+1}\cdots a_{j-1}]a_j \text{ is a chain}.

First-order logic (FO) quantifies over positions; monadic second-order logic (MSO) also quantifies over sets of positions. These are logics of the structured words, rather than logics whose domain is the nodes of their OP trees.

Precedence-Oriented Temporal Logic (POTL) is interpreted on the same OP-word structures. It extends linear temporal reasoning with modalities that navigate the chain structure. POTL is expressively equivalent to FO with one free variable on finite OP words [7 Theorem 4.9]. We say that L⊆L(M)L \subseteq L(M) is POTL-definable if there is a POTL formula φ\varphi such that

L={w∈L(M)∣(w,0)⊨φ},L = \{w \in L(M) \mid(w,0) \models\varphi\},

where position 0 carries the initial boundary marker #.

Operator-precedence expressions (OPEs) extend regular expressions with Boolean operations and a fence operation that tests the parenthesized structure assigned by MM. We use the syntax and semantics of [17]. An OPE is star-free if it uses neither Kleene star nor positive iteration. The totality convention in that reference is without loss of generality: undefined entries of MM can be enforced by its hole constraints after completing MM [17 Section 3]. These constraints admit star-free expressions, and a completion adding only ⋖\lessdot or ⋗\gtrdot entries preserves acyclicity. The same reference establishes the equivalence of FO definability, star-free OPEs, and non-counting of the associated parenthesized language under the acyclicity hypotheses used here. The precise non-counting condition is recalled in the aperiodicity section, where it is related to OPTA aperiodicity.

Finally, a finite monoid VV is aperiodic if there exists N≥1N \geq1 such that vN=vN+1v^N = v^{N+1} for every v∈Vv \in V. In this paper, the relevant monoids consist of transformations induced by tree contexts.

OP Tree Automata

Let Σ\Sigma be a finite alphabet and let MM be an operator-precedence matrix over Σ\Sigma. Write L(M)⊆Σ+L(M) \subseteq\Sigma^+ for the set of words compatible with MM.

Let TΣ\mathcal{T}_{\Sigma} be the set of all finite ordered trees whose leaves are labeled in Σ\Sigma, whose internal nodes are labeled ∙\bullet, and whose root is an internal node. Every internal node has a positive, otherwise unrestricted, number of children. Membership in TΣ\mathcal{T}_{\Sigma} does not require compatibility with MM.

For w∈L(M)w \in L(M), let TM(w)T_M(w) denote its operator-precedence tree, obtained from the unique chain decomposition determined by MM. Each chain reduction contributes one internal node labeled ∙\bullet, and the leaves carry the letters of ww in their original order. The children of a chain node are its skeleton terminals and the trees of its subchains, in left-to-right order; boundary markers are omitted.

For L⊆L(M)L \subseteq L(M), write

TM(L)={TM(w)∣w∈L},UM=TM(L(M)).T_M(L) = \{T_M(w) \mid w \in L\}, \qquad U_M = T_M(L(M)).

Thus UMU_M is the universe of valid OP trees for MM, and

TM(L)⊆UM⊆TΣ∙.T_M(L) \subseteq U_M \subseteq\mathcal{T}_{\Sigma}^{\bullet}.

Definition 1 (Operator-precedence tree automaton). An OPTAOPTA is a tuple

A=(Σ,M,Q,F,(Hq)q∈Q),\mathcal{A}=(\Sigma,M,Q,F,(H_q)_{q\in Q}),

where Σ\Sigma is a finite terminal alphabet, MM is an OPMOPM over Σ\Sigma, QQ is a finite set of states, also called vertical states, F⊆QF\subseteq Q is the set of final states, and each

Hq⊆(Σ⊎Q)+,H_q\subseteq(\Sigma\uplus Q)^{+},

where ⊎\uplus denotes disjoint union, is a regular language, called the horizontal transition language associated with qq.1

Let t∈TΣ∙t\in T_{\Sigma}^{\bullet}. A run of A\mathcal{A} on tt is a mapping ρ:Int⁡(t)→Q\rho:\operatorname{Int}(t)\to Q such that, for every internal node vv with ordered children v1,…,vkv_1,\ldots,v_k,

λρ(v1)⋯λρ(vk)∈Hρ(v),\lambda_\rho(v_1)\cdots\lambda_\rho(v_k)\in H_{\rho(v)},

where

λρ(u)={a,if u is a leaf labeled a∈Σ,ρ(u),if u is an internal node.\lambda_\rho(u)= \begin{cases} a, & \text{if } u \text{ is a leaf labeled } a\in\Sigma,\\ \rho(u), & \text{if } u \text{ is an internal node.} \end{cases}

Thus, terminal children contribute their labels, whereas internal children contribute their computed states.

The run is accepting if ρ(root⁡(t))∈F\rho(\operatorname{root}(t))\in F. The unrestricted tree language Tree⁡(A)\operatorname{Tree}(\mathcal{A}) consists of all t∈TΣ∙t\in T_{\Sigma}^{\bullet} admitting an accepting run. The word language recognized by A\mathcal{A} is

L(A)={w∈L(M)∣TM(w) admits an accepting run of A}.L(\mathcal{A})=\{w\in L(M)\mid T_M(w)\text{ admits an accepting run of }\mathcal{A}\}.

Horizontal words containing adjacent vertical states cannot occur in runs on valid OP trees and therefore do not affect L(A)L(\mathcal{A}). They may still occur in the horizontal languages of complete recognizers, whose runs are also defined on invalid trees.

An OPTAOPTA is deterministic when its horizontal languages are pairwise disjoint. Deterministic and nondeterministic OPTAOPTA recognize the same languages, by bottom-up tree-automaton determinization [CDG+08].

Example 1 (Matching pairs with even depth). Let Σ={a,b}\Sigma=\{a,b\} and consider the language L={a2nb2n∣n≥1}L=\{a^{2n}b^{2n}\mid n\geq1\}.

We fix the OPMOPM MM such that a⋖aa\lessdot a, b⋗bb\gtrdot b, and a.=ba\mathrel{.=}b, with the usual boundary relations; all other entries are undefined.

The following automaton accepts LL:

A=(Σ,M,{q0,q1},{q0},(Hq0,Hq1)),\mathcal{A}=(\Sigma,M,\{q_0,q_1\},\{q_0\},(H_{q_0},H_{q_1})),
Hq0={aq1b},Hq1={ab,aq0b}.H_{q_0}=\{aq_1b\},\qquad H_{q_1}=\{ab,aq_0b\}.

The horizontal languages are disjoint, so A\mathcal{A} is deterministic. Its runs alternate q1q_1 and q0q_0 along the nested abab-pairs, accepting exactly when the number of pairs is even.

For instance, the accepting run on TM(aabb)=∙(a,∙(a,b),b)T_M(aabb)=\bullet(a,\bullet(a,b),b) is shown in Figure 1.

Figure 1. Accepting run on TM(aabb)=∙(a,∙(a,b),b)T_M(aabb)=\bullet(a,\bullet(a,b),b); states are written beside internal nodes.

OPTA Define OP Languages

Throughout, MM is a conflict-free operator-precedence matrix; no acyclicity assumption is made. In the cyclic case, the grammatical counterpart is a cyclic operator-precedence grammar (C-OPG), whose production right-hand sides are regular expressions, in the sense of [8].

Theorem 1 (From cyclic OPGs to OPTA). Let G=(Σ,VN,P,S)G=(\Sigma,V_N,P,S) be a C-OPG with OPM⁡(G)⊆M\operatorname{OPM}(G)\subseteq M. There is an effectively constructible OPTA AG\mathcal{A}_G over (Σ,M)(\Sigma,M) such that

L(AG)=L(G).L(\mathcal{A}_G)=L(G).

Proof. For every nonterminal A∈VNA\in V_N, let

HA=⋃A→r∈PL(r).H_A=\bigcup_{A\to r\in P}L(r).

where L(r)⊆(Σ⊎VN)+L(r)\subseteq(\Sigma\uplus V_N)^{+} is the regular language denoted by the production expression rr. Define

AG=(Σ,M,VN,S,(HA)A∈VN).\mathcal{A}_G=(\Sigma,M,V_N,S,(H_A)_{A\in V_N}).

Each HAH_A is regular.

For w∈L(G)w\in L(G), choose a derivation tree in which each production occurrence A→rA\to r is instantiated by some word in L(r)L(r). Replacing its internal labels by ∙\bullet yields TM(w)T_M(w), because OPM⁡(G)⊆M\operatorname{OPM}(G)\subseteq M. The nonterminal labels give an accepting run of AG\mathcal{A}_G.

Conversely, an accepting run on TM(w)T_M(w) assigns a nonterminal AA to each internal node whose sequence of terminal children and states of internal children belongs to HAH_A. Choose a production A→rA\to r witnessing this membership. These choices yield a derivation tree of ww in GG.

Theorem 2 (From OPTA to OPA). For every OPTA

A=(Σ,M,Q,F,(Hq)q∈Q)\mathcal{A}=(\Sigma,M,Q,F,(H_q)_{q\in Q})

there is an effectively constructible OPA B\mathcal{B} using the same matrix MM such that

L(B)=L(A).L(\mathcal{B})=L(\mathcal{A}).

In particular, this holds when MM has ==-cycles.

Proof. Since the languages HqH_q are regular, their complete deterministic recognizers can be combined into one finite deterministic device with state set SS, initial state s0s_0, transition function

δˉ:S×(Σ⊎Q)→S,\bar{\delta}: S \times(\Sigma\uplus Q) \to S,

and output function

out⁡:S→2Q\operatorname{out}: S \to2^Q

such that, for every u∈(Σ⊎Q)∗u \in(\Sigma\uplus Q)^*,

out⁡(δˉ∗(s0,u))={q∈Q∣u∈Hq}.\operatorname{out}(\bar{\delta}^*(s_0,u)) = \{q \in Q \mid u \in H_q\}.

The OPA B\mathcal{B} has control-state set

QB=S×(Q∪{↓}),Q_B = S \times(Q \cup\{\downarrow\}),

where ↓∉Q\downarrow\notin Q denotes the absence of a pending subtree state. In a state (s,x)(s,x), the first component summarizes the horizontal word processed so far, while x∈Qx \in Q, if present, is the state of a completed subtree not yet incorporated into that word. For convenience, extend δˉ\bar{\delta} by

δˉ(s,↓)=s.\bar{\delta}(s,\downarrow) = s.

We use the standard OPA convention: a push stores the current control state on the stack, a shift preserves this saved state, and a pop transition receives the current state and the saved state of the removed stack entry. The initial state of B\mathcal{B} is (s0,↓)(s_0,\downarrow), while the set of final states is {(s0,q)∣q∈F}\{(s_0,q) \mid q \in F\}. For a∈Σa \in\Sigma, define

δpush((s,x),a)={(δˉ(δˉ(s0,x),a),↓)},\delta_{\mathrm{push}}((s,x),a) = \{(\bar{\delta}(\bar{\delta}(s_0,x),a),\downarrow)\},
δshift((s,x),a)={(δˉ(δˉ(s,x),a),↓)},\delta_{\mathrm{shift}}((s,x),a) = \{(\bar{\delta}(\bar{\delta}(s,x),a),\downarrow)\},
δpop((s,x),(t,y))={(t,q)∣q∈out⁡(δˉ(s,x))}.\delta_{\mathrm{pop}}((s,x),(t,y)) = \{(t,q) \mid q \in\operatorname{out}(\bar{\delta}(s,x))\}.

As usual, MM determines whether a push, shift, or pop is performed. A push starts a new horizontal computation from s0s_0. If a subtree state is pending, it is read first, as the leftmost child of the new chain node. A shift extends the current horizontal computation, first reading any pending subtree state and then the terminal. A pop reads any pending rightmost subtree state, chooses the state of the completed chain node, and restores the suspended horizontal state tt. The saved component yy is not restored: when present, it was already incorporated as the leftmost child at the matching push.

To prove correctness, we establish the following invariant by induction on chain trees. For any chain with tree tt, and any s∈Ss \in S, its support in B\mathcal{B}, starting in control state (s,↓)(s,\downarrow), can finish in (s,q)(s,q) if and only if tt admits a run of A\mathcal{A} with root state qq. The support consumes the chain body and returns to the same underlying stack prefix. Write the chain body as

w0a1w1⋯akwk,k≥1.w_0a_1w_1\cdots a_kw_k,\qquad k\ge1.

For each nonempty subchain wiw_i, let qiq_i be its chosen root state, and put

zi={qi,wi≠ε,ε,wi=ε.z_i=\begin{cases} q_i, & w_i\ne\varepsilon,\\ \varepsilon, & w_i=\varepsilon. \end{cases}

By the induction hypothesis, processing a nonempty wiw_i preserves the surrounding horizontal state and leaves qiq_i pending. The push on a1a_1, the subsequent shifts, and the final pop therefore feed the horizontal device exactly the word

u=z0a1z1⋯akzk.u=z_0a_1z_1\cdots a_kz_k.

The pop can select exactly the states q∈out⁡(δ⃗∗(s0,u))q\in\operatorname{out}(\vec{\delta}^{*}(s_0,u)), i.e., those satisfying u∈Hqu\in H_q. These are precisely the possible root states of an OPTA run on tt. The pop restores the first component ss saved by the matching push. This proves the invariant in both directions; the case with no subchains is its base case.

Applying the invariant to the outer chain #[w]#\#[w]\# shows that B\mathcal{B} finishes with empty stack in (s0,q)(s_0,q) exactly when TM(w)T_M(w) has a run with root state qq. Both devices use the same matrix, so words outside L(M)L(M) cannot be accepted. The set of final states of B\mathcal{B} gives L(B)=L(A)L(\mathcal{B})=L(\mathcal{A}). □

Hence, OPTA have the same expressive power as OPAs and C-OPGs, defining the operator-precedence languages over arbitrary conflict-free matrices, including cyclic ones.

Canonical recognition and minimality

Let LL be an OPTA language on (Σ,M)(\Sigma,M) with no acyclicity assumption for MM. We use the unranked universe TΣ∙\mathcal{T}_{\Sigma}^{\bullet} and its subset UMU_M of valid OP trees. In this setting, a context has exactly one hole for a tree of TΣ∙\mathcal{T}_{\Sigma}^{\bullet}; the identity context □\square is included. We call CΣ∙\mathcal{C}_{\Sigma}^{\bullet} the set of these contexts.

Exact recognition

By Definition 1, Tree⁡(A)\operatorname{Tree}(\mathcal{A}) is the unrestricted tree language of A\mathcal{A}. Recognition of the word language LL therefore requires only

Tree⁡(A)∩UM=TM(L).\operatorname{Tree}(\mathcal{A})\cap U_M=T_M(L).

Definition 2. An OPTA is an exact recognizer of (M,L)(M,L) if

Tree⁡(A)=TM(L).\operatorname{Tree}(\mathcal{A})=T_M(L).

It therefore rejects every tree outside UMU_M.

Throughout the minimality results, a normalized complete deterministic OPTA has pairwise disjoint horizontal languages satisfying

Hq⊆(Σ⊎Q)+,⋃q∈QHq=(Σ⊎Q)+.H_q \subseteq(\Sigma\uplus Q)^+, \qquad\bigcup_{q\in Q} H_q = (\Sigma\uplus Q)^+.

The positive-arity normalization is already part of Definition 1. Its size for the minimality statements is ∣Q∣|Q|, the number of vertical states; terminal labels and states of auxiliary horizontal word automata are not counted in QQ.

The exactness requirement fixes the behavior on invalid trees. The following example shows why this matters for uniqueness.

Example 2 (Recognition restricted to valid inputs). Let Σ={x,a,b,c}\Sigma= \{x,a,b,c\}. Set every terminal-pair precedence relation to ≫\mathrel{\gg}, except

x⋖a,x⋖c,x \mathrel{\lessdot} a,\qquad x \mathrel{\lessdot} c,

and use the usual boundary relations. For L={xa}L = \{xa\}, consider two complete deterministic OPTA with states {p,q,r}\{p,q,r\}, final state rr, and the following horizontal output functions:

horizontal wordA1\mathcal{A}_1A2\mathcal{A}_2
aapppp
bbppqq
ccqqqq
xpxprrrr
every other wordqqqq

Table 2.

Their unrestricted accepted tree languages are

Tree⁡(A1)={∙(x,∙(a)),∙(x,∙(b))},Tree⁡(A2)={∙(x,∙(a))}.\operatorname{Tree}(\mathcal{A}_1)=\{\bullet(x,\bullet(a)),\bullet(x,\bullet(b))\},\qquad\operatorname{Tree}(\mathcal{A}_2)=\{\bullet(x,\bullet(a))\}.

However,

TM(xa)=∙(x,∙(a)),TM(xb)=∙(∙(x),b).T_M(xa)=\bullet(x,\bullet(a)),\qquad T_M(xb)=\bullet(\bullet(x),b).

Thus, the extra tree accepted by A1\mathcal{A}_1 is invalid for MM, and both OPTA recognize the same word language LL.

Both require three vertical states among deterministic devices having a run on every valid input. Indeed, ∙(a)\bullet(a) and ∙(c)\bullet(c) must reach distinct nonfinal states: the context ∙(x,□)\bullet(x,\square) gives valid trees for xaxa and xcxc, and distinguishes them. An accepting state for xaxa is distinct from both. Nevertheless, the two displayed automata are not isomorphic: A1\mathcal{A}_1 assigns the same state to ∙(a)\bullet(a) and ∙(b)\bullet(b), while A2\mathcal{A}_2 does not. Hence, minimum recognition on valid inputs alone need not be canonical, even for an acyclic matrix.

The canonical exact OPTA

For a complete deterministic OPTA A\mathcal{A}, denote by eA(t)e_{\mathcal{A}}(t) the unique state computed at the root of tt. The automaton is reduced if each of its states equals eA(t)e_{\mathcal{A}}(t) for some t∈TΣ∙t \in T_{\Sigma}^{\bullet}.

Lemma 1. If LL is recognized by an OPTAOPTA over (Σ,M)(\Sigma, M), then TM(L)T_M(L) is a regular unranked tree language and has an effectively constructible reduced complete deterministic exact OPTAOPTA.

Proof. Choose an equivalent C-OPG GG with OPM⁡(G)⊆M\operatorname{OPM}(G) \subseteq M. Its derivation trees, with nonterminal labels erased, form a regular unranked tree language: each nonterminal supplies one state, and the finite union of its production expressions supplies the corresponding regular horizontal language. Every accepted derivation tree has underlying tree TM(w)T_M(w) for its yield ww, and every w∈Lw \in L has such a derivation. Hence, this tree language is exactly TM(L)T_M(L).

Apply bottom-up determinization and completion, then remove unreachable states. These operations are effective for regular horizontal languages. In particular, the subset construction retains all possible nonterminal states at each node; its horizontal transition languages are regular by closure under finite Boolean operations and finite letter substitutions. □\square

Definition 3. For s,t∈TΣ∙s,t \in T_\Sigma^\bullet, define

s≡M,Lt⟺∀C∈CΣ∙ (C[s]∈TM(L)⟺C[t]∈TM(L)).s \equiv_{M,L} t \quad\Longleftrightarrow\quad\forall C \in C_\Sigma^\bullet\ \bigl(C[s] \in T_M(L) \Longleftrightarrow C[t] \in T_M(L)\bigr).

Write [t][t] for the equivalence class of tt and define

QM,L=TΣ∙/≡M,L.Q_{M,L}=T_\Sigma^\bullet/{\equiv_{M,L}}.

Lemma 2. The equivalence ≡M,L\equiv_{M,L} has finite index. Moreover, replacing an internal-rooted child by an equivalent tree preserves the equivalence class of its parent tree.

Proof. Let D\mathcal{D} be a reduced complete deterministic exact recognizer with state set QDQ_D. If eD(s)=eD(t)e_D(s)=e_D(t), then every context computes the same root state on ss and tt, and hence s≡M,Lts \equiv_{M,L} t. Therefore, the index of ≡M,L\equiv_{M,L} is at most ∣QD∣\lvert Q_D\rvert.

For substitution, fix all other children and any outer context. The resulting expression is itself a one-hole context. The defining equivalence therefore permits the replacement. Replacing several children one at a time gives the corresponding simultaneous-substitution property. □\square

For a horizontal word α∈(Σ⊎QM,L)+\alpha\in(\Sigma\uplus Q_{M,L})^+, replace each state symbol [t][t] by an arbitrary representative tree and each terminal symbol by its leaf, and place a ∙\bullet-root above the resulting sequence. Denote the resulting tree by rep⁡(α)\operatorname{rep}(\alpha). Lemma 2 shows that its equivalence class is independent of the chosen representatives. Hence, the function

μM,L:(Σ⊎QM,L)+→QM,L,μM,L(α)=[rep⁡(α)]\mu_{M,L} : (\Sigma\uplus Q_{M,L})^+ \to Q_{M,L}, \qquad\mu_{M,L}(\alpha)=[\operatorname{rep}(\alpha)]

is well defined.

Definition 4 (Canonical exact OPTA). The canonical exact OPTA for (M,L)(M,L) is

AM,Lmin⁡=(Σ,M,QM,L,FM,L,(Hcmin⁡)c∈QM,L),(1)\mathcal{A}^{\min}_{M,L}=(\Sigma,M,Q_{M,L},F_{M,L},(H^{\min}_c)_{c\in Q_{M,L}}), \tag*{(1)}

where

FM,L={[t]∣t∈TM(L)},Hcmin⁡={α∈(Σ⊎QM,L)+∣μM,L(α)=c}.F_{M,L}=\{[t]\mid t\in T_M(L)\},\qquad H^{\min}_c=\{\alpha\in(\Sigma\uplus Q_{M,L})^+\mid\mu_{M,L}(\alpha)=c\}.

For complete deterministic OPTA A\mathcal{A} and A′\mathcal{A}' over (Σ,M)(\Sigma,M), write μA\mu_{\mathcal{A}} and μA′\mu_{\mathcal{A}'} for their horizontal output functions. A homomorphism from A\mathcal{A} to A′\mathcal{A}' is a map φ:Q→Q′\varphi:Q\to Q' whose extension φˉ\bar{\varphi} to horizontal words fixes terminals and satisfies

φ(μA(α))=μA′(φˉ(α)),q∈F⟺φ(q)∈F′,\varphi(\mu_{\mathcal{A}}(\alpha))=\mu_{\mathcal{A}'}(\bar{\varphi}(\alpha)),\qquad q\in F\Longleftrightarrow\varphi(q)\in F',

for every α∈(Σ⊎Q)+\alpha\in(\Sigma\uplus Q)^+ and q∈Qq\in Q.

Theorem 3. For every OPTA language LL over an OPM MM:

  1. AM,Lmin⁡A^{\min}_{M,L} is a finite reduced normalized complete deterministic exact OPTA;

  2. every reduced normalized complete deterministic exact OPTA for (M,L)(M,L) admits a unique surjective homomorphism onto AM,Lmin⁡A^{\min}_{M,L};

  3. AM,Lmin⁡A^{\min}_{M,L} has the minimum number of vertical states among such exact recognizers, and every minimum recognizer is isomorphic to it.

Isomorphism identifies horizontal languages after renaming vertical states; it does not identify arbitrary syntactic representations of these regular languages.

Proof. Finiteness of QM,LQ_{M,L} follows from Lemma 2. We first verify that the horizontal languages are regular. Let

D=(Σ,M,P,FD,(Gp)p∈P)\mathcal{D}=(\Sigma,M,P,F_{\mathcal{D}},(G_p)_{p\in P})

be a reduced normalized complete deterministic exact recognizer. Define

π:P⟶QM,L,π(eD(t))=[t].\pi:P\longrightarrow Q_{M,L},\qquad\pi(e_{\mathcal{D}}(t))=[t].

This is well defined by the first part of the proof of Lemma 2, and it is surjective. Extend π\pi to a letter-to-letter homomorphism

h:(Σ⊎P)∗⟶(Σ⊎QM,L)∗h:(\Sigma\uplus P)^*\longrightarrow(\Sigma\uplus Q_{M,L})^*

that fixes each terminal. Then, for every c∈QM,Lc\in Q_{M,L},

Hcmin⁡=h(⋃p∈Pπ(p)=cGp).(2)H^{\min}_c=h\left(\bigcup_{\substack{p\in P\\ \pi(p)=c}}G_p\right). \tag*{(2)}

Indeed, every horizontal word over PP can be realized by choosing representative trees for its state symbols. Its image under hh computes the class of that same parent tree. Conversely, every class symbol has a representative among the reachable states of D\mathcal{D}. Equation (1) proves regularity.

The languages Hcmin⁡H^{\min}_c partition all horizontal words, so the automaton is normalized, complete, and deterministic. Induction on trees gives

EM,Lmin⁡(t)=[t].\mathcal{E}^{\min}_{M,L}(t)=[t].

It follows both that every state is reachable and that the accepted tree language is exactly TM(L)T_M(L).

For any reduced complete deterministic exact recognizer D\mathcal{D}, the same map π\pi preserves transitions: if μD(α)\mu_D(\alpha) denotes the unique state selected by the horizontal word α\alpha, then

π(μD(α))=μM,L(h(α)).\pi(\mu_D(\alpha))=\mu_{M,L}(h(\alpha)).

It also preserves and reflects finality:

p∈FD⟺π(p)∈FM,L.p\in F_D\Longleftrightarrow\pi(p)\in F_{M,L}.

Thus, π\pi is a surjective automaton homomorphism. Any homomorphism must send the value of each tree tt to [t][t], so it is uniquely determined because D\mathcal{D} is reduced.

Hence, every reduced complete deterministic exact recognizer has at least ∣QM,L∣|Q_{M,L}| vertical states. If it has exactly that many, π\pi is bijective and therefore an isomorphism.

The canonical recognizer is effectively constructible. Obtain D\mathcal{D} by Lemma 1. A product of deterministic word automata for the languages GpG_p gives a finite Moore machine computing μD\mu_D on nonempty words. Its reachable prefix states and its finite monoid of suffix transformations allow us to enumerate all maps

gα,β:P→P,gα,β(p)=μD(αpβ),α,β∈(Σ⊎P)∗.g_{\alpha,\beta}:P\to P,\qquad g_{\alpha,\beta}(p)=\mu_D(\alpha p\beta),\qquad\alpha,\beta\in(\Sigma\uplus P)^*.

Since D\mathcal{D} is reduced, each such map is induced by an elementary tree context. Conversely, every tree context decomposes along the path from its hole to its root into elementary contexts. Closing these maps under composition and adding the identity therefore computes the finite set VDV_D of all context transformations on PP. Now compute

p∼q⟺∀v∈VD (v(p)∈FD⟺v(q)∈FD).p\sim q\qquad\Longleftrightarrow\qquad\forall v\in V_D\ (v(p)\in F_D\Longleftrightarrow v(q)\in F_D).

By exactness and reducedness, p∼qp\sim q holds exactly when π(p)=π(q)\pi(p)=\pi(q). Thus P/∼P/{\sim} effectively represents QM,LQ_{M,L}, and Equation (2) constructs its regular horizontal languages. □

This is the tree-context Myhill–Nerode construction specialized to the OPTA convention of terminal leaves and a single internal label.

The ranked presentation for acyclic matrices

For the aperiodicity analysis of the next section, we also need a ranked presentation of the exact tree language. In this subsection, assume that MM is acyclic. Define B=2∣Σ∣+1B = 2|\Sigma| + 1, ΓM=Σ∪{∙k∣1≤k≤B}\Gamma_M = \Sigma\cup\{\bullet_k \mid1 \le k \le B\}, where terminals have rank zero and ∙k\bullet_k has rank kk. Call TΓMT_{\Gamma_M} the set of all trees over this ranked alphabet. Relabeling each ∙\bullet-node of arity kk by ∙k\bullet_k identifies the trees in TΣT_\Sigma of arity at most BB with TΓM∖ΣT_{\Gamma_M} \setminus\Sigma; here Σ\Sigma denotes the set of one-leaf terminal trees. We use this identification implicitly and retain the notation TM(L)T_M(L) for the ranked image. Since every valid OP tree has arity at most BB, we have TM(L)⊆TΓMT_M(L) \subseteq T_{\Gamma_M}; TΓMT_{\Gamma_M} also contains invalid trees and single terminal leaves.

We apply the standard Myhill-Nerode construction for ranked tree languages [CDG+08, Section 1.5] to the language TM(L)T_M(L). The resulting automaton recognizes precisely TM(L)T_M(L) and therefore rejects every tree outside the valid OP-tree universe.

Definition 5 (Canonical minimal ranked tree automaton). A tree context is a ranked tree with exactly one hole, into which a single tree can be substituted. For s,t∈TΓMs,t \in T_{\Gamma_M}, define

s≡M,Lrkt⟺∀C (C[s]∈TM(L)⟺C[t]∈TM(L)).s \mathrel{\equiv^{\mathrm{rk}}_{M,L}} t \quad\Longleftrightarrow\quad\forall C\ (C[s] \in T_M(L) \Longleftrightarrow C[t] \in T_M(L)).

The canonical minimal recognizer BM,LB_{M,L} has state set Q^M,L=TΓM/≡M,Lrk\widehat{Q}_{M,L} = T_{\Gamma_M}/{\equiv^{\mathrm{rk}}_{M,L}}. Writing [t]rk[t]_{\mathrm{rk}} for the class of tt, its transitions are

Δa=[a]rk,Δ∙k([t1]rk,…,[tk]rk)=[∙k(t1,…,tk)]rk,\Delta_a = [a]_{\mathrm{rk}}, \qquad\Delta_{\bullet_k}([t_1]_{\mathrm{rk}},\ldots,[t_k]_{\mathrm{rk}}) = [\bullet_k(t_1,\ldots,t_k)]_{\mathrm{rk}},

and its final states are {[t]rk∣t∈TM(L)}\{[t]_{\mathrm{rk}} \mid t \in T_M(L)\}.

By Lemma 1 and the arity bound, TM(L)T_M(L) is a regular ranked tree language. The equivalence therefore has finite index, and its quotient is the reduced minimal complete deterministic ranked tree automaton recognizing exactly TM(L)T_M(L). In particular, it rejects trees that are not MM-compatible. As with the unranked construction, minimality concerns exact recognition, not behavior specified only on MM-compatible inputs.

The automata AM,Lmin⁡A^{\min}_{M,L} and BM,LB_{M,L} use different state-counting conventions. The unranked congruence ≡M,L\equiv_{M,L} has domain TΣT_\Sigma and uses the contexts in CΣC_\Sigma; its quotient counts only states assigned to internal-rooted trees. The ranked congruence ≡M,Lrk\equiv^{\mathrm{rk}}_{M,L} instead uses ranked contexts on all of TΓMT_{\Gamma_M}, including terminal leaves, so BM,LB_{M,L} also evaluates leaves in its state set. The original OPTA continues to treat terminal children by their labels. Moreover, the unranked exact recognizer must reject every tree containing a node with more than BB children, whereas such trees lie outside TΓMT_{\Gamma_M}. Section 5 uses BM,LB_{M,L} for the acyclic aperiodicity characterization.

Tree-context aperiodicity for acyclic matrices

Section 4 supplies canonical recognizers of the exact OP-tree language. Following the context-aperiodicity framework of [EI07], we study the transformations induced by tree contexts on their states. For acyclic matrices, the ranked presentation yields a characterization of balanced non-counting, and hence of first-order definability, POTL definability, and star-free OPEs under the stated hypotheses.

Throughout this section, let MM be acyclic and let L⊆L(M)L \subseteq L(M) be an OPTA language. We use the arity bound BB, ranked alphabet ΓM\Gamma_M, and canonical minimal ranked tree automaton BM,LB_{M,L} introduced in § 4.3.

Definition 6 (Context aperiodicity). Let B\mathcal{B} be a reduced complete deterministic ranked tree automaton with state set Q^\widehat{Q}. Every tree context CC induces a transformation

τC:Q^→Q^.\tau_C:\widehat{Q}\to\widehat{Q}.

For the canonical recognizer, this transformation is τC([t]rk)=[C[t]]rk\tau_C([t]_{\mathrm{rk}})=[C[t]]_{\mathrm{rk}}. The context transition monoid is

V(B)={τC∣C is a tree context},V(\mathcal{B})=\{\tau_C\mid C\text{ is a tree context}\},

with composition and identity induced by context substitution. The automaton is aperiodic if there exists N≥1N\geq1 such that

τN=τN+1\tau^N=\tau^{N+1}

for every τ∈V(B)\tau\in V(\mathcal{B}). We call the canonical OPTA presentation of LL aperiodic when BM,L\mathcal{B}_{M,L} has this property.

We recall the standard counter-free characterization of context aperiodicity [9].

Theorem 4 (Counter-free characterization). For an automaton B\mathcal{B} as above, aperiodicity is equivalent to

τCm(q)=q⟹τC(q)=q\tau_C^m(q)=q\quad\Longrightarrow\quad\tau_C(q)=q

for every context CC, state q∈Q^q\in\widehat{Q}, and integer m≥1m\geq1. If these conditions hold, then

τ∣Q^∣=τ∣Q^∣+1\tau^{|\widehat{Q}|}=\tau^{|\widehat{Q}|+1}

for every τ∈V(B)\tau\in V(\mathcal{B}). Hence, ∣Q^∣|\widehat{Q}| is an exponent witnessing aperiodicity.

Proof. A transformation of a finite set has eventually constant powers exactly when every cycle in its functional graph has length one. In that case every state reaches a fixed point within ∣Q^∣|\widehat{Q}| steps. This observation can be applied to every transformation in V(B)V(\mathcal{B}). □\square

Let ⟨\langle and ⟩\rangle be two fresh parenthesis symbols. The parenthesis encoding is

η(a)=a,η(∙k(t1,…,tk))=⟨η(t1)⋯η(tk)⟩.\eta(a)=a,\qquad\eta(\bullet_k(t_1,\ldots,t_k))=\langle\eta(t_1)\cdots\eta(t_k)\rangle.

Set ⟨L⟩=η(TM(L))\langle L\rangle=\eta(T_M(L)). The encoding is injective and, on valid OP trees, agrees with the canonical parenthesization of [17]: each internal node contributes the pair of parentheses surrounding one production application in an equivalent OP grammar. We use the non-counting condition of [17 Definitions 2.11 and 2.14]: there exists n0≥2n_0 \ge2 such that, for all x,u,z,v,yx,u,z,v,y with zz and uzvuzv well-parenthesized,

xun0zvn0y∈L⟺xun0+mzvn0+my∈L(m≥0).(3)xu^{n_0}zv^{n_0}y \in\mathcal{L} \quad\Longleftrightarrow\quad xu^{n_0+m}zv^{n_0+m}y \in\mathcal{L}\qquad(m \ge0). \tag*{(3)}

The next lemma accounts for the fact that a balanced factor can encode a forest, rather than a single subtree. For this auxiliary argument, a forest [3] is a finite ordered sequence of trees built from terminal leaves a∈Σa \in\Sigma and ∙\bullet-nodes of arbitrary arity, including zero. We identify a tree with its singleton forest, denote the empty forest by 00, and write ++ for concatenation. The notation ∙(f)\bullet(f) denotes the tree whose root has label ∙\bullet and whose ordered sequence of children is ff.

A forest context contains exactly one hole □\square in a sequence of siblings, possibly at the top level. Formally, such contexts are generated by

P::=□∣f+P+g∣∙(P),P ::= \square\mid f + P + g \mid\bullet(P),

where ff and gg range over forests. Substitution P[f]P[f] replaces the hole by the entire sequence ff; substitution of 00 deletes the hole. For example, for P=∙(a+□+b)P = \bullet(a + \square+ b),

P[c+d]=∙(a+c+d+b),P[0]=∙(a+b).P[c+d] = \bullet(a+c+d+b), \qquad P[0] = \bullet(a+b).

Composition and powers are defined by substitution as for tree contexts: P0=□P^0 = \square and Pn+1=P[Pn]P^{n+1} = P[P^n].

The parenthesis encoding extends to these forests by

η(0)=ε,η(f+g)=η(f)η(g),η(∙(f))=⟨η(f)⟩.\eta(0) = \varepsilon,\qquad\eta(f+g) = \eta(f)\eta(g),\qquad\eta(\bullet(f)) = \langle\eta(f)\rangle.

We view K⊆TΓMK \subseteq T_{\Gamma_M} as a forest language containing only its single-tree members, identifying each ∙k\bullet_k with ∙\bullet of arity kk.

Lemma 3. Let K⊆TΓMK \subseteq T_{\Gamma_M}. Suppose that for some N≥1N \ge1, all ranked tree contexts C,DC,D, and all t∈TΓMt \in T_{\Gamma_M},

D[CN[t]]∈K⟺D[CN+1[t]]∈K.(4)D[C^N[t]] \in K \quad\Longleftrightarrow\quad D[C^{N+1}[t]] \in K. \tag*{(4)}

Then, with n0=max⁡{B+1,N+1}n_0 = \max\{B+1,N+1\}, for all forest contexts P,DP,D, all forests ff, and all n≥n0n \ge n_0,

D[Pn[f]]∈K⟺D[Pn+1[f]]∈K.(5)D[P^n[f]] \in K \quad\Longleftrightarrow\quad D[P^{n+1}[f]] \in K. \tag*{(5)}

Proof. (4) also holds with any exponent n≥Nn \ge N, by replacing tt with Cn−N[t]C^{n-N}[t].

First, suppose the hole of PP has no parent. Then P[f]=hℓ+f+hrP[f] = h_\ell+f+h_r for fixed forests hℓ,hrh_\ell,h_r. If both are empty, PP is the identity. Otherwise Pn[f]P^n[f] has more than BB roots for n>Bn > B. Substitution into DD therefore produces either several top-level trees or a node with more than BB children. In either case membership in KK is impossible.

Then, suppose the hole has a parent. There are fixed forests hℓ,hrh_\ell,h_r and a forest context UU that yields a single tree under every forest substitution, such that P[f]=hℓ+U[f]+hrP[f]=h_\ell+U[f]+h_r. Define a one-tree context E[t]=U[hℓ+t+hr]E[t]=U[h_\ell+t+h_r] and put t∗=U[f]t_*=U[f]. A direct induction gives Pn[f]=hℓ+En−1[t∗]+hrP^n[f]=h_\ell+E^{n-1}[t_*]+h_r, n≥1n\ge1. With D′[t]=D[hℓ+t+hr]D'[t]=D[h_\ell+t+h_r], we obtain D[Pn[f]]=D′[En−1[t∗]]D[P^n[f]]=D'[E^{n-1}[t_*]].

If t∗t_* is not a tree of TΓMT_{\Gamma_M}, or EE or D′D' is not a ranked tree context over ΓM\Gamma_M, the resulting forest cannot belong to KK for any n≥2n\ge2: it contains a forbidden arity (including zero) or has more than one root. Such a defect persists under substitution of a single tree; for n≥2n\ge2, the expression contains both t∗t_* and at least one copy of EE. Otherwise, apply (3) with context EE, outer context D′D', and exponent n−1≥Nn-1\ge N. This proves (4).

Theorem 5 (Aperiodicity and non-counting for acyclic OPTA). Let MM be acyclic, and let LL be recognized by an OPTA over (Σ,M)(\Sigma,M). The following conditions are equivalent:

  1. (L ⁣M)(\mathord{\mathrm{L}}_{\!M}) satisfies the balanced non-counting condition (3).

  1. The canonical minimal ranked tree automaton BM,L\mathcal{B}_{M,L} is aperiodic.

  1. There exists an aperiodic reduced complete deterministic ranked tree automaton recognizing exactly TM(L)T_M(L).

Proof. (1) implies (2). Let n0n_0 witness (2). For arbitrary tree contexts C,DC,D and tree tt, write

η(C[t])=uη(t)v,η(D[t])=xη(t)y.\eta(C[t])=u\eta(t)v,\qquad\eta(D[t])=x\eta(t)y.

Here the strings u,vu,v depend only on CC, and x,yx,y only on DD. Putting z=η(t)z=\eta(t) gives

η(D[Cn[t]])=xunzvny.\eta(D[C^n[t]])=x u^n z v^n y.

Both zz and uzvuzv are well-parenthesized. The non-counting condition therefore yields

D[Cn0[t]]∈TM(L)⟺D[Cn0+1[t]]∈TM(L).D[C^{n_0}[t]]\in T_M(L)\Longleftrightarrow D[C^{n_0+1}[t]]\in T_M(L).

Since this holds for every outer context DD,

Cn0[t]≡M,LrkCn0+1[t].C^{n_0}[t]\mathrel{\equiv^{\mathrm{rk}}_{M,L}}C^{n_0+1}[t].

Every state of the canonical recognizer is represented by a tree, so τCn0=τCn0+1\tau_C^{n_0}=\tau_C^{n_0+1} for every CC.

(2) implies (3). Take the canonical recognizer itself.

(3) implies (1). Let B\mathcal{B} recognize exactly TM(L)T_M(L), with aperiodicity exponent NN. Evaluation in B\mathcal{B} immediately gives (3). Lemma 3 gives (4) with uniform threshold n0=max⁡{B+1,N+1}n_0=\max\{B+1,N+1\}.

Any well-parenthesized word zz encodes a forest ff. A well-parenthesized factor of a well-parenthesized word encodes a consecutive sequence of siblings

at some depth, possibly at the top level. Replacing that sequence by a hole gives a forest context; an empty factor corresponds to an insertion position. If uzvuzv is also well-parenthesized, then u□vu\Box v encodes a forest context PP, and

η(Pn[f])=unzvn.\eta(P^n[f])=u^n z v^n.

If xunzvnyx u^n z v^n y is well-parenthesized for some nn, then x□yx\Box y similarly defines an outer forest context DD. Replacing its balanced middle factor by any other forest encoding preserves well-parenthesization, so the same DD works for every exponent. If there is no such nn, all the relevant words lie outside (L⊔)(L\mathbin{\sqcup}). Hence, (4) gives equality of membership at every pair of consecutive exponents at least n0n_0. Iterating these equivalences proves (2) for every m≥0m\ge0. □

Corollary 1 (First-order logic, temporal logic, and star-freeness). Under the hypotheses of Theorem 5, the following are equivalent:

  1. BM,LB_{M,L} is aperiodic;

  2. LL is definable in first-order logic over OP words, with order, letter predicates, and the chain relation;

  3. LL is definable by a star-free operator-precedence expression;

  4. LL is definable by a POTL formula over finite OP words, evaluated at the initial boundary position.

Proof. Combine Theorem 5 with [17 Theorems 4.2, 4.3, 5.4, and 7.26]. The equivalence of conditions (2) and (4) follows from [7 Theorem 4.9]. For the language-level equivalence, an FO sentence can be viewed as a formula with a dummy free variable and translated into POTL, evaluated at position 0. Conversely, the FO translation of a POTL formula is made into a sentence by requiring its free variable to denote the least position. □

Corollary 2. Aperiodicity of the canonical minimal ranked tree automaton BM,LB_{M,L} is decidable.

Proof. Construct and minimize a reduced complete deterministic ranked recognizer of TM(L)T_M(L), and let Q^\widehat{Q} be its state set. Generate the context transition monoid from the identity and the elementary maps

q↦Δ∙,k(q1,…,qi−1,q,qi+1,…,qk),q\mapsto\Delta_{\bullet,k}(q_1,\ldots,q_{i-1},q,q_{i+1},\ldots,q_k),

for all 1≤k≤B1\le k\le B, all 1≤i≤k1\le i\le k, and all fixed choices of the other states. Since the automaton is reduced, these maps are induced by proper tree contexts. Conversely, every context is a composition of elementary contexts, so these maps generate the entire monoid.

The generated monoid has at most ∣Q^∣∣Q^∣|\widehat{Q}|^{|\widehat{Q}|} elements. By Theorem 4, test τ∣Q^∣=τ∣Q^∣+1\tau^{|\widehat{Q}|}=\tau^{|\widehat{Q}|+1} for every generated transformation τ\tau. □

Note that even when every horizontal transition language HqH_q is finite, iteration of a tree context can cycle through distinct states. Therefore, aperiodicity of the individual word languages HqH_q does not characterize aperiodicity of the OPTA.

Conclusions

The concept of OPTA offers a useful bridge from the theory of Tree Automata to the one of Operator Precedence languages that we used to obtain the following results:

  • We proved that OPTA recognize exactly the OPLs. The equivalence holds for arbitrary conflict-free matrices, including cyclic ones.

  • We constructed an effectively computable canonical complete deterministic exact OPTA, minimal in its number of vertical states.

  • We characterized balanced non-counting by aperiodicity of the context transition monoid of the canonical minimal ranked tree recognizer, in the setting of acyclic matrices. Combined with [17], this yields an

equivalence with first-order definability over OP words and with star-free operator-precedence expressions. By [7], these conditions are also equivalent to POTL definability.

An overview of the updated results is presented in Figure 2, where the boxes represent the languages defined by the following notations: OPTAAP\mathrm{OPTA}_{\mathrm{AP}} denotes languages whose canonical ranked recognizer is aperiodic; Monadic Second Order logic for OP is MSO, and FO its first-order fragment; POTL denotes Precedence-Oriented Temporal Logic; OP expressions are OPE, and OPESF\mathrm{OPE}_{\mathrm{SF}} their star-free fragment; OPGAP\mathrm{OPG}_{\mathrm{AP}} are the aperiodic OP grammars; OPSC denotes the characterization by the finite-index OP syntactic congruence of [12].

Figure 2. Overview of the main results for OPLs with acyclic matrices: 1 stands for [13], 2 for [17], 3 for [12], 4 for [7], and 5 (shown in blue) for results proved here.

References

  1. [1]Rajeev Alur and Parthasarathy Madhusudan. Adding nesting structure to words. J. ACM, 56(3), 2009.
  2. [2]Alessandro Barenghi, Stefano Crespi Reghizzi, Dino Mandrioli, Federica Panella, and Matteo Pradella. Parallel parsing made practical. Sci. Comput. Program., 112(3):195–226, 2015.DOI
  3. [3]Mikolaj Bojańczyk and Igor Walukiewicz. Forest algebras. In Jörg Flum, Erich Grädel, and Thomas Wilke, editors, Logic and Automata: History and Perspectives, volume 2 of Texts in Logic and Games, pages 107–132. Amsterdam University Press, 2008.
  4. [5]Julien Cristau, Christof Löding, and Wolfgang Thomas. Deterministic automata on unranked trees. In Foundations of Semistructured Data, volume 05061 of Dagstuhl Seminar Proceedings, pages 1–12, 2005.
  5. [6]Stefano Crespi Reghizzi and Dino Mandrioli. Operator Precedence and the Visibly Pushdown Property. J. Comput. Syst. Sci., 78(6):1837–1867, 2012.
  6. [7]Michele Chiari, Dino Mandrioli, and Matteo Pradella. A first-order complete temporal logic for structured context-free languages. Logical Methods in Computer Science, 18(3), 2022.DOI
  7. [8]Michele Chiari, Dino Mandrioli, and Matteo Pradella. Cyclic operator precedence grammars for parallel parsing. Inf. Comput., 307:105363, 2025.arxiv.org/abs/2309.04200
  8. [9][ÉI07] Zoltán Ésik and Szabolcs Iván. Aperiodicity in tree automata. In Algebraic Informatics, 2nd International Conference, CAI, pages 189–207, 2007.DOI
  9. [10][Flo63] Robert W. Floyd. Syntactic Analysis and Operator Precedence. J. ACM, 10(3):316–333, 1963.DOI
  10. [11][Heu91] Uschi Heuter. First-order properties of trees, star-free expressions, and aperiodicity. ITA, 25:125–145, 1991.
  11. [12][HKMS23] Thomas A. Henzinger, Pavol Kĕbis, Nicolas Mazzocchi, and N. Ege Saraç. Regular methods for operator precedence languages. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10–14, 2023, Paderborn, Germany, volume 261 of LIPIcs, pages 129:1–129:20, 2023.
  12. [13][LMPP15] Violetta Lonati, Dino Mandrioli, Federica Panella, and Matteo Pradella. Operator precedence languages: Their automata-theoretic and logic characterization. SIAM J. Comput., 44(4):1026–1088, 2015.DOI
  13. [14][Meh80] Kurt Mehlhorn. Pebbling mountain ranges and its application of DCFL-recognition. In Automata, languages and programming (ICALP-80), volume 85 of LNCS, pages 422–435, 1980.
  14. [15][MP71] Robert McNaughton and Seymour Papert. Counter-free Automata. MIT Press, Cambridge, USA, 1971.
  15. [16][MP18] Dino Mandrioli and Matteo Pradella. Generalizing input-driven languages: Theoretical and practical benefits. Computer Science Review, 27:61–87, 2018.arxiv.org/abs/1705.00984
  16. [17][MPC23] Dino Mandrioli, Matteo Pradella, and Stefano Crespi Reghizzi. Aperiodicity, star-freeness, and first-order definability of operator precedence languages. Logical Methods in Computer Science, 19(4), 2023.DOI
  17. [18][Sal73] Arto K. Salomaa. Formal Languages. Academic Press, New York, NY, 1973.

Paper details

vlnc:W_tcu77fgc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents