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 , it already acts as a recognizer of the compatible-word language and determines a canonical tree 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 need not preserve the separately constructed trees of and 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 , 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 . The objects being compared are internal-rooted trees, and the tests are substitutions into arbitrary one-hole tree contexts, with membership in 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, is a finite nonempty alphabet, is the empty word, and . We study languages of nonempty words; empty factors and auxiliary languages containing are nevertheless allowed. The symbol , not in , delimits words, and .
Trees and tree automata
All trees are finite, rooted, and ordered. For a tree , we write for its root and 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 assigns an arity to each symbol; 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 of arity , a total transition function ; for , this specifies a state for the leaf . 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 , with regular, permits state at an -node precisely when its child-state word belongs to [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 in place of a subtree. We write for substitution of into the hole, and for composition of contexts. Iteration is defined by and .
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
We write , , or when 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
The pair is an OP alphabet. Matrix inclusion is entrywise: means that every relation specified by is also specified by . The matrix is total if every terminal-pair entry is defined, and acyclic if the directed graph of on has no cycle.
Chains describe the structure induced by independently of grammar nonterminals. A simple chain, written , has , , , defined, and
A composed chain has the form
where is a simple chain and, for each , either or is recursively a chain. The symbols are its boundaries, the word between brackets is its body, and is its skeleton.
A word is compatible with if is a chain. We denote the set of such words by . 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 gives at most children. If is acyclic, its skeletons have no repeated terminal, so ; thus OP trees have arity at most . Cyclic matrices do not impose any arity bound.
Grammars and operator-precedence automata
We use grammars with a finite nonterminal set disjoint from , a finite production set , and a nonempty set of axioms . 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
where ranges over . The induced matrix collects the relations
together with the boundary relations for the terminal sets of the axioms and . An operator grammar is an operator-precedence grammar (OPG) when 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 chooses a word 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 , initial and final sets , a matrix , and transition functions
Stack entries are pairs , above a bottom marker whose terminal symbol is . Let be the current state, the top terminal, and the next input symbol. The matrix determines the move:
If , consume , push , and choose a state in .
If , consume , replace the top entry by , and choose a state in .
If , remove and choose a state in , without consuming .
Shift and pop require a nonbottom entry. Acceptance starts with stack and a state in , and ends with stack , a state in , and only the final unread. An undefined relation blocks the run. A support of a chain is the computation fragment that reads its body , with 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 , set . The associated word structure has domain , the linear order , letter predicates for , and the chain relation
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 is POTL-definable if there is a POTL formula such that
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 . 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 can be enforced by its hole constraints after completing [17 Section 3]. These constraints admit star-free expressions, and a completion adding only or 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 is aperiodic if there exists such that for every . In this paper, the relevant monoids consist of transformations induced by tree contexts.
OP Tree Automata
Let be a finite alphabet and let be an operator-precedence matrix over . Write for the set of words compatible with .
Let be the set of all finite ordered trees whose leaves are labeled in , whose internal nodes are labeled , and whose root is an internal node. Every internal node has a positive, otherwise unrestricted, number of children. Membership in does not require compatibility with .
For , let denote its operator-precedence tree, obtained from the unique chain decomposition determined by . Each chain reduction contributes one internal node labeled , and the leaves carry the letters of 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 , write
Thus is the universe of valid OP trees for , and
Definition 1 (Operator-precedence tree automaton). An is a tuple
where is a finite terminal alphabet, is an over , is a finite set of states, also called vertical states, is the set of final states, and each
where denotes disjoint union, is a regular language, called the horizontal transition language associated with .1
Let . A run of on is a mapping such that, for every internal node with ordered children ,
where
Thus, terminal children contribute their labels, whereas internal children contribute their computed states.
The run is accepting if . The unrestricted tree language consists of all admitting an accepting run. The word language recognized by is
Horizontal words containing adjacent vertical states cannot occur in runs on valid OP trees and therefore do not affect . They may still occur in the horizontal languages of complete recognizers, whose runs are also defined on invalid trees.
An is deterministic when its horizontal languages are pairwise disjoint. Deterministic and nondeterministic recognize the same languages, by bottom-up tree-automaton determinization [CDG+08].
Example 1 (Matching pairs with even depth). Let and consider the language .
We fix the such that , , and , with the usual boundary relations; all other entries are undefined.
The following automaton accepts :
The horizontal languages are disjoint, so is deterministic. Its runs alternate and along the nested -pairs, accepting exactly when the number of pairs is even.
For instance, the accepting run on is shown in Figure 1.
Figure 1. Accepting run on ; states are written beside internal nodes.
OPTA Define OP Languages
Throughout, 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 be a C-OPG with . There is an effectively constructible OPTA over such that
Proof. For every nonterminal , let
where is the regular language denoted by the production expression . Define
Each is regular.
For , choose a derivation tree in which each production occurrence is instantiated by some word in . Replacing its internal labels by yields , because . The nonterminal labels give an accepting run of .
Conversely, an accepting run on assigns a nonterminal to each internal node whose sequence of terminal children and states of internal children belongs to . Choose a production witnessing this membership. These choices yield a derivation tree of in .
Theorem 2 (From OPTA to OPA). For every OPTA
there is an effectively constructible OPA using the same matrix such that
In particular, this holds when has -cycles.
Proof. Since the languages are regular, their complete deterministic recognizers can be combined into one finite deterministic device with state set , initial state , transition function
and output function
such that, for every ,
The OPA has control-state set
where denotes the absence of a pending subtree state. In a state , the first component summarizes the horizontal word processed so far, while , if present, is the state of a completed subtree not yet incorporated into that word. For convenience, extend by
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 is , while the set of final states is . For , define
As usual, determines whether a push, shift, or pop is performed. A push starts a new horizontal computation from . 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 . The saved component 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 , and any , its support in , starting in control state , can finish in if and only if admits a run of with root state . The support consumes the chain body and returns to the same underlying stack prefix. Write the chain body as
For each nonempty subchain , let be its chosen root state, and put
By the induction hypothesis, processing a nonempty preserves the surrounding horizontal state and leaves pending. The push on , the subsequent shifts, and the final pop therefore feed the horizontal device exactly the word
The pop can select exactly the states , i.e., those satisfying . These are precisely the possible root states of an OPTA run on . The pop restores the first component 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 shows that finishes with empty stack in exactly when has a run with root state . Both devices use the same matrix, so words outside cannot be accepted. The set of final states of gives . □
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 be an OPTA language on with no acyclicity assumption for . We use the unranked universe and its subset of valid OP trees. In this setting, a context has exactly one hole for a tree of ; the identity context is included. We call the set of these contexts.
Exact recognition
By Definition 1, is the unrestricted tree language of . Recognition of the word language therefore requires only
Definition 2. An OPTA is an exact recognizer of if
It therefore rejects every tree outside .
Throughout the minimality results, a normalized complete deterministic OPTA has pairwise disjoint horizontal languages satisfying
The positive-arity normalization is already part of Definition 1. Its size for the minimality statements is , the number of vertical states; terminal labels and states of auxiliary horizontal word automata are not counted in .
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 . Set every terminal-pair precedence relation to , except
and use the usual boundary relations. For , consider two complete deterministic OPTA with states , final state , and the following horizontal output functions:
| horizontal word | ||
| every other word |
Table 2.
Their unrestricted accepted tree languages are
However,
Thus, the extra tree accepted by is invalid for , and both OPTA recognize the same word language .
Both require three vertical states among deterministic devices having a run on every valid input. Indeed, and must reach distinct nonfinal states: the context gives valid trees for and , and distinguishes them. An accepting state for is distinct from both. Nevertheless, the two displayed automata are not isomorphic: assigns the same state to and , while 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 , denote by the unique state computed at the root of . The automaton is reduced if each of its states equals for some .
Lemma 1. If is recognized by an over , then is a regular unranked tree language and has an effectively constructible reduced complete deterministic exact .
Proof. Choose an equivalent C-OPG with . 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 for its yield , and every has such a derivation. Hence, this tree language is exactly .
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.
Definition 3. For , define
Write for the equivalence class of and define
Lemma 2. The equivalence has finite index. Moreover, replacing an internal-rooted child by an equivalent tree preserves the equivalence class of its parent tree.
Proof. Let be a reduced complete deterministic exact recognizer with state set . If , then every context computes the same root state on and , and hence . Therefore, the index of is at most .
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.
For a horizontal word , replace each state symbol by an arbitrary representative tree and each terminal symbol by its leaf, and place a -root above the resulting sequence. Denote the resulting tree by . Lemma 2 shows that its equivalence class is independent of the chosen representatives. Hence, the function
is well defined.
Definition 4 (Canonical exact OPTA). The canonical exact OPTA for is
where
For complete deterministic OPTA and over , write and for their horizontal output functions. A homomorphism from to is a map whose extension to horizontal words fixes terminals and satisfies
for every and .
Theorem 3. For every OPTA language over an OPM :
is a finite reduced normalized complete deterministic exact OPTA;
every reduced normalized complete deterministic exact OPTA for admits a unique surjective homomorphism onto ;
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 follows from Lemma 2. We first verify that the horizontal languages are regular. Let
be a reduced normalized complete deterministic exact recognizer. Define
This is well defined by the first part of the proof of Lemma 2, and it is surjective. Extend to a letter-to-letter homomorphism
that fixes each terminal. Then, for every ,
Indeed, every horizontal word over can be realized by choosing representative trees for its state symbols. Its image under computes the class of that same parent tree. Conversely, every class symbol has a representative among the reachable states of . Equation (1) proves regularity.
The languages partition all horizontal words, so the automaton is normalized, complete, and deterministic. Induction on trees gives
It follows both that every state is reachable and that the accepted tree language is exactly .
For any reduced complete deterministic exact recognizer , the same map preserves transitions: if denotes the unique state selected by the horizontal word , then
It also preserves and reflects finality:
Thus, is a surjective automaton homomorphism. Any homomorphism must send the value of each tree to , so it is uniquely determined because is reduced.
Hence, every reduced complete deterministic exact recognizer has at least vertical states. If it has exactly that many, is bijective and therefore an isomorphism.
The canonical recognizer is effectively constructible. Obtain by Lemma 1. A product of deterministic word automata for the languages gives a finite Moore machine computing on nonempty words. Its reachable prefix states and its finite monoid of suffix transformations allow us to enumerate all maps
Since 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 of all context transformations on . Now compute
By exactness and reducedness, holds exactly when . Thus effectively represents , 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 is acyclic. Define , , where terminals have rank zero and has rank . Call the set of all trees over this ranked alphabet. Relabeling each -node of arity by identifies the trees in of arity at most with ; here denotes the set of one-leaf terminal trees. We use this identification implicitly and retain the notation for the ranked image. Since every valid OP tree has arity at most , we have ; 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 . The resulting automaton recognizes precisely 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 , define
The canonical minimal recognizer has state set . Writing for the class of , its transitions are
and its final states are .
By Lemma 1 and the arity bound, 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 . In particular, it rejects trees that are not -compatible. As with the unranked construction, minimality concerns exact recognition, not behavior specified only on -compatible inputs.
The automata and use different state-counting conventions. The unranked congruence has domain and uses the contexts in ; its quotient counts only states assigned to internal-rooted trees. The ranked congruence instead uses ranked contexts on all of , including terminal leaves, so 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 children, whereas such trees lie outside . Section 5 uses 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 be acyclic and let be an OPTA language. We use the arity bound , ranked alphabet , and canonical minimal ranked tree automaton introduced in § 4.3.
Definition 6 (Context aperiodicity). Let be a reduced complete deterministic ranked tree automaton with state set . Every tree context induces a transformation
For the canonical recognizer, this transformation is . The context transition monoid is
with composition and identity induced by context substitution. The automaton is aperiodic if there exists such that
for every . We call the canonical OPTA presentation of aperiodic when has this property.
We recall the standard counter-free characterization of context aperiodicity [9].
Theorem 4 (Counter-free characterization). For an automaton as above, aperiodicity is equivalent to
for every context , state , and integer . If these conditions hold, then
for every . Hence, 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 steps. This observation can be applied to every transformation in .
Let and be two fresh parenthesis symbols. The parenthesis encoding is
Set . 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 such that, for all with and well-parenthesized,
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 and -nodes of arbitrary arity, including zero. We identify a tree with its singleton forest, denote the empty forest by , and write for concatenation. The notation denotes the tree whose root has label and whose ordered sequence of children is .
A forest context contains exactly one hole in a sequence of siblings, possibly at the top level. Formally, such contexts are generated by
where and range over forests. Substitution replaces the hole by the entire sequence ; substitution of deletes the hole. For example, for ,
Composition and powers are defined by substitution as for tree contexts: and .
The parenthesis encoding extends to these forests by
We view as a forest language containing only its single-tree members, identifying each with of arity .
Lemma 3. Let . Suppose that for some , all ranked tree contexts , and all ,
Then, with , for all forest contexts , all forests , and all ,
Proof. (4) also holds with any exponent , by replacing with .
First, suppose the hole of has no parent. Then for fixed forests . If both are empty, is the identity. Otherwise has more than roots for . Substitution into therefore produces either several top-level trees or a node with more than children. In either case membership in is impossible.
Then, suppose the hole has a parent. There are fixed forests and a forest context that yields a single tree under every forest substitution, such that . Define a one-tree context and put . A direct induction gives , . With , we obtain .
If is not a tree of , or or is not a ranked tree context over , the resulting forest cannot belong to for any : it contains a forbidden arity (including zero) or has more than one root. Such a defect persists under substitution of a single tree; for , the expression contains both and at least one copy of . Otherwise, apply (3) with context , outer context , and exponent . This proves (4).
Theorem 5 (Aperiodicity and non-counting for acyclic OPTA). Let be acyclic, and let be recognized by an OPTA over . The following conditions are equivalent:
satisfies the balanced non-counting condition (3).
The canonical minimal ranked tree automaton is aperiodic.
There exists an aperiodic reduced complete deterministic ranked tree automaton recognizing exactly .
Proof. (1) implies (2). Let witness (2). For arbitrary tree contexts and tree , write
Here the strings depend only on , and only on . Putting gives
Both and are well-parenthesized. The non-counting condition therefore yields
Since this holds for every outer context ,
Every state of the canonical recognizer is represented by a tree, so for every .
(2) implies (3). Take the canonical recognizer itself.
(3) implies (1). Let recognize exactly , with aperiodicity exponent . Evaluation in immediately gives (3). Lemma 3 gives (4) with uniform threshold .
Any well-parenthesized word encodes a forest . 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 is also well-parenthesized, then encodes a forest context , and
If is well-parenthesized for some , then similarly defines an outer forest context . Replacing its balanced middle factor by any other forest encoding preserves well-parenthesization, so the same works for every exponent. If there is no such , all the relevant words lie outside . Hence, (4) gives equality of membership at every pair of consecutive exponents at least . Iterating these equivalences proves (2) for every . □
Corollary 1 (First-order logic, temporal logic, and star-freeness). Under the hypotheses of Theorem 5, the following are equivalent:
is aperiodic;
is definable in first-order logic over OP words, with order, letter predicates, and the chain relation;
is definable by a star-free operator-precedence expression;
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 is decidable.
Proof. Construct and minimize a reduced complete deterministic ranked recognizer of , and let be its state set. Generate the context transition monoid from the identity and the elementary maps
for all , all , 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 elements. By Theorem 4, test for every generated transformation . □
Note that even when every horizontal transition language is finite, iteration of a tree context can cycle through distinct states. Therefore, aperiodicity of the individual word languages 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: 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 their star-free fragment; 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]Rajeev Alur and Parthasarathy Madhusudan. Adding nesting structure to words. J. ACM, 56(3), 2009.
- [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]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.
- [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.
- [6]Stefano Crespi Reghizzi and Dino Mandrioli. Operator Precedence and the Visibly Pushdown Property. J. Comput. Syst. Sci., 78(6):1837–1867, 2012.
- [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
- [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
- [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
- [10][Flo63] Robert W. Floyd. Syntactic Analysis and Operator Precedence. J. ACM, 10(3):316–333, 1963.DOI
- [11][Heu91] Uschi Heuter. First-order properties of trees, star-free expressions, and aperiodicity. ITA, 25:125–145, 1991.
- [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.
- [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
- [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.
- [15][MP71] Robert McNaughton and Seymour Papert. Counter-free Automata. MIT Press, Cambridge, USA, 1971.
- [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
- [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
- [18][Sal73] Arto K. Salomaa. Formal Languages. Academic Press, New York, NY, 1973.

