Learning Tree Automata with Term Rewriting

1 Introduction

Active automata learning. The aim of active automata learning is to generate a deterministic finite automaton (DFA) recognizing an unknown regular language L (target language) having access to an oracle answering queries about L, i.e., the algorithm is allowed to actively query about the language in contrast to passive learning where the input dataset does not change. There are two types of queries: membership of a given word in L, and equivalence of the language of a given DFA A with the target language L, where the answer to an equivalence query is either YES, or a counterexample word distinguishing L and L(A). This framework was proposed in the seminal paper [Angluin, 1987] along with the L∗ algorithm, which enables learning in polynomial time. Active automata learning has been intensively studied for both efficiency [Isberner et al., 2014; Vaandrager et al., 2022] as well as extensions to other automata-based models. In particular, the L∗ algorithm has been adapted to tree automata [Drewes and H¨ogberg, 2003] and multiplicity tree automata [Habrard and Oncina, 2006; Marusic and Worrell, 2015].

Applications of active tree-automata learning. Trees are a natural model for structured data and hence tree automata are often used in knowledge representation, including processing of XML, JSON, and unification in Description Logics [Baader and Narendran, 1998]. Motivated by these applications, active learning of tree languages and related formalisms has been extensively studied and applied to information extraction [Kosala et al., 2003], the synthesis of node specifications [Grienenberger and Ritzert, 2019], structured data transformations [Yaghmazadeh et al., 2016], and Description Logic EL terminologies [Magnini et al., 2025]. Due to the close link between regular tree and context-free languages, active learning of tree languages has been applied to context-free grammar repair [Raselimo and Fischer, 2021], learning probabilistic grammars [Nitay et al., 2021], and verification and explainability of RNNs [Barbot et al., 2021].

Query complexity. The number of queries required by the L∗ algorithm is polynomial in the size of the target automaton. While it is feasible to answer that many queries automatically, the number remains too high for manual intervention. Consequently, there is a large body of work on improving query complexity of active automata learning [Isberner et al., 2014; Frohme, 2019; Vaandrager et al., 2022; Kruger et al., 2024; Dierl et al., 2024] as well as implementing the teacher using Large Language Models [Magnini et al., 2025; Bhattamishra et al., 2026; Vazquez-Chanlatte et al., 2025]. However, LLMs only answer membership queries, and their equivalence query answers are merely approximations with a large number of membership queries. This approximation approach is similar to prior work on automating query answering [Vaandrager, 2017]. Therefore, in this work, we follow an alternative route, proposed in [Fica and Otop, 2025], which is to restrict the search space of automata by providing the learning algorithm with additional information (called advice) regarding the target language. Furthermore, we focus on inferring the answers to equivalence queries as it yields the greatest reduction in complexity and increases reliability of learning (answers to these queries are often approximated). We briefly discuss how to infer answers to membership queries.

Learning with advice. We consider an extended learning framework, in which the learning algorithm is given advice about the target language [Fica and Otop, 2025]. This advice constrains the search space and allows the algorithm to infer answers to certain queries. This approach bridges two synthesis paradigms: deductive synthesis from specifications and inductive synthesis based on queries. Furthermore, it allows for flexibility to express the learned language partially with queries and partially with a term rewriting system (TRS), which substantially differs from automata, and hence some properties can be succinctly expressed with a TRS instead of multiple queries.

Term rewriting as advice. A Term Rewriting System (TRS) consists of rewrite rules l → r, where l, r are terms (or equivalently trees with variables). Rewriting is the process of iteratively transforming a tree by replacing an instance of a left-hand side l with its corresponding right-hand side r. For example:

• Commutativity: The rule f(X, Y ) → f(Y,X) allows for the swapping of subtrees at node f.
• Associativity: With f(f(X, Y ),Z) → f(X, f(Y,Z)) any tree with f symbols and constants can be transformed into a right skewed tree.

In our approach, an advice TRS defines an equivalence relation relative to the target language L. Specifically, if a tree t is in L, then all trees obtained by rewriting t must be in L. Similarly rewriting is compatible with the complement of L. We also consider one-sided relations stating that (1) trees from L are rewritten to trees from L only, while there are no restrictions for trees not in L, or (2) trees not in L are rewritten to trees not in L only. This allows the TRS to capture highlevel structural properties, such as symmetry or associativity of a given symbol, while it is not expected to characterize the learned language completely.

Contributions. Active automata learning with advice has been already introduced for finite automata on words [Fica and Otop, 2025]. In this paper we study automata over trees and present the following substantial contributions:

1. We develop an algorithm that infers answers to equivalence queries for tree automata (Section 3). The transition to trees introduces distinct technical challenges absent in the word case. In particular, general inference is computationally difficult. We therefore identify subclasses of TRSs that admit tractable inference.
2. To illustrate the efficacy of the advice mechanism, we provide TRSs expressing natural tree language properties and show, through experimental evaluation, a significant reduction in query complexity (Section 4).
3. Finally, we introduce the synthesis problem for TRS for a given regular tree language, which is the converse of active learning with advice: given a regular tree language, find a TRS consistent with it. We establish a connection between synthesis of TRS and the classical problem of finding synchronizing words in DFA (Section 5).

The extended version of the paper is available at [Kopystia´nski and Otop, 2026a], while the code and experiments data are available at [Kopystia´nski and Otop, 2026b].

Relatedwork. A large body of work focuses on optimizing the computational and query complexity of the L∗ algorithm for word automata [Isberner et al., 2014; Frohme, 2019; Vaandrager et al., 2022; Dierl et al., 2024] and tree automata [Drewes and H¨ogberg, 2007; Kasprzik, 2013]. These works are orthogonal to our approach, as our algorithm is compatible with any active learning algorithm using equivalence queries. Our work directly extends [Fica and Otop, 2025] to the tree setting. Independently, enhancing the performance of active tree automaton learning by restricting focus to specific subclasses of tree languages remains an active area of research [van Heerdt et al., 2021; Bj¨orklund et al., 2017]. Furthermore, extending the types of queries to improve the efficiency of active learning has also been investigated [Tirn˘auc˘a and Tirn˘auc˘a, 2007].

2 Preliminaries

A signature (or ranked alphabet) F is a pair (F, Ar) consisting of the set of symbols F and a function Ar : F → N assigning a unique arity to each symbol. To ease the notation, we will write f ∈ F meaning f ∈ F .

2.1 Terms

For a signature F and a set of variables X, the set of terms over F and X, denoted by T (F,X), is the least set containing X such that for all f ∈ F, if k = Ar(f) and t1, . . . , tk ∈ T (F,X), then f(t1, . . . , tk) ∈ T (F,X). In particular, if a ∈ F and Ar(a) = 0, then a ∈ T (F,X). The set of ground terms T (F) over the signature F is the set T (F, ∅), i.e., terms containing no variables. We consider signatures F that contain at least one constant symbol, as otherwise T (F) is empty. A term t is linear if every variable occurs at most once in t.

A substitution σ is a function from variables to terms with a finite domain. Each substitution σ can be uniquely extended to ̂ σ over all terms T (F,X) as follows: for X ∈ X we have ̂ σ(X) = σ(X) if X ∈ dom(σ) and otherwise ̂ σ(X) = X. For a term t, which is not a variable, we have t = f(t1, . . . , tk), and ̂ σ(t) = f(̂ σ(t1), . . . , ̂ σ(tk)). Since the extension from σ to ̂ σ is unique, we refer to ̂ σ as σ. For a variable X and terms t, s, we denote by t[X → s] the term σs(t) resulting from the substitution σs(X) = s.

2.2 Trees as Terms

A (ranked) tree over F is a ground term over F and we refer to T (F) as the set of trees over F. Referring to ranked trees as ground terms is common in the literature [Comon et al., 2008]. In the unranked case, when symbols do not have unique arities, the order-based definition of trees is required, but in this paper we consider only ranked trees.

A context c is a term with a single occurrence of a variable X. For a context c and a tree (ground term) t, we define c(t) = c[X → t], i.e., the substitution σ(X) = t applied to c.

2.3 Tree Automata

A bottom-up deterministic finite tree automaton (DFTA) is a tuple (F,Q,Qacc, δ) consisting of the signature F, a finite set of states Q, a set of accepting states Qacc, and a transition function δ : Q∗ × F → Q. The transition function δ is a partial function such that δ(u, f) is defined if and only if |u| is equal to Ar(f). We extend δ to a function ̂ δ : T (F) → Q inductively:

1. If t is a constant c ∈ F, then ̂ δ(c) is the unique state q such that δ(c) = q.
2. If t = f(t1, . . . , tk), then ̂ δ(t) = δ(̂ δ(t1), . . . , ̂ δ(tk), f ). The tree language recognized by A, denoted by L(A), is the set of all trees such that ̂ δ(t) is an accepting state, i.e., L(A) = {t | ̂ δ(t) ∈ Qacc}.

2.4 Myhill-Nerode Theorem for Tree Languages

For a tree language L over F we define ∼L on trees over F as follows: for all trees t1, t2 over F we have t1 ∼L t2 if and only if c(t1) ∈ L ↔ c(t2) ∈ L, for every context c over F.

Lemma 1. A tree language L is regular if and only if ∼L has finitely many equivalence classes.

Furthermore, for every regular tree language L a minimal DFTA recognizing L exists and it is unique (up to an isomorphism). The states of the minimal DFTA for L correspond to equivalence classes of ∼L. Note that all states in the minimal DFTA are reachable.

2.5 Learning Tree Automata

The framework of active tree-automata learning assumes an oracle, called minimally adequate teacher, which answers two types of queries about the target tree language L:

• membership queries: given a tree t ∈ T (F), is t ∈ L?, and
• equivalence queries: given a DFTA A, is L(A) = L? If not the teacher returns a counterexample, which is a tree from exactly one of the sets L(A) and L.

The tree-automata variant of the L∗ algorithm [Drewes and H¨ogberg, 2003] having access to the oracle for a tree language L returns the minimal DFTA AL recognizing L. It works in polynomial time in |AL| and the total size of counterexamples supplied by the oracle. Unlike the wordautomaton case, where the shortest counterexample is linear in the size of the minimal DFA, a minimal-size counterexample tree can be of exponential size. However, if counterexamples are presented as directed acyclic graphs (DAGs), their size remains polynomially bounded in |AL| [Charatonik, 1999; Anantharaman et al., 2005].

2.6 TermRewriting Systems

A term rewriting system (TRS) R over a signature F is a finite set of pairs of terms (l, r) over F. A pair of terms (l, r) from R is called a rewrite rule and denoted by l → r. For a TRS R, we define a single-step rewrite relation →R over terms from T (F,X) as the least relation such that (i) for all substitutions σ and all rules (l, r) from R we have σ(l) →R σ(r), and (ii) for all f ∈ F, if k is the arity of f and s →R t, then for all terms s1, . . . , sk-1 and all i we have f(s1, . . . , si-1, s, si+1, . . . , sk) →R f(s1, . . . , si-1, t, si+1, . . . , sk). The rewriting relation →∗R is the transitive and reflexive closure of →R. We will omit the R subscript if the TRS is clear from the context.

Normal forms. A term t is in a normal form if there is no t′ such that t →R t′ . If for a term s there is a unique t in a normal form such that s →∗R t, we say that t is the normal form of s (w.r.t. R) and denote it by NFR(s).

Computing normal forms. A (finite) TRS R is terminating if every sequence of terms s0, s1, . . . such that si → si+1 is finite, confluent if for all terms s, s1, s2, if s →∗ s1 and s →∗ s2, then there is t such that s1 →∗ t and s2 →∗ t, and convergent if it is terminating and confluent. In a convergent TRS, every term s has the (unique) normal form, which can be computed by applying reductions in an arbitrary order as long as the term can be reduced. Termination guarantees that this process takes finitely many steps and confluence entails the uniqueness of the result. Therefore, for a convergent TRS R, one can effectively compute NFR(s). However, showing that a TRS is convergent is generally difficult [Baader and Nipkow, 1998].

3 Learning Tree AutomataWith Advice

In this section, we adapt the framework of active learning with advice [Fica and Otop, 2025] to tree automata. We first formally define the active learning problem with advice, then discuss how to resolve queries using that advice.

In our framework, advice for the learning algorithm is given via TRSs, which relate to tree languages through the following notions of consistency:

Definition 2 ([Fica and Otop, 2025]). Let F be a signature, R be a TRS over F and L be a (regular) tree language over F. We say that

• R is (fully) consistent with L if and only if for all trees s, t, if s →∗R t, then s ∈ L ⇐⇒ t ∈ L.
• R is positively consistent with L if and only if for all trees s, t, if s →∗R t, then s ∈ L =⇒ t ∈ L.
• R is negatively consistent with L if and only if for all trees s, t, if s →∗R t, then s /∈ L =⇒ t /∈ L.

Note that a TRS R is fully consistent with L if and only if it is both positively and negatively consistent. While more granular than standard consistency, positive and negative consistency are harder to infer.

Having the notions of consistency, we can formally state the active learning with advice problem.

Definition 3. The active tree-automata learning with advice problem for an unknown regular tree language U is as follows:

• Input: (1) an oracle answering membership and equivalence queries about the target regular tree language U, and (2) three advice TRSs: R=, which is consistent with U, and R+,R-, which are respectively positively and negatively consistent with U.
• Output: the minimal DFTA that recognizes U.

Reducing equivalence queries with advice. To reduce the number of equivalence queries, the algorithm first checks whether an advice TRS R is consistent (resp., positively or negatively consistent) with the language of a candidate automaton A before querying the oracle. If it is not consistent, an equivalence query is unnecessary because L(A) must differ from the target language with which R is known to be consistent (resp., positively or negatively consistent). In such cases, the algorithm computes a pair of trees violating consistency (resp., positive or negative consistency). For example, for positive consistency, violating trees s, t are such that s →∗R t but s ∈ L(A) =⇒ t ∈ L(A) does not hold. One of the trees s or t has to be the counterexample to L(A) being equal to the target language. The algorithm decides which one with a single membership query.

Remark 4 (Rewrite rules vs. regular languages). Rewrite rules can express non-regular properties. For example, f(X, X) → a expresses that the value of a tree with identical immediate subtrees the same as the value of a with respect to L. Tree automata cannot express equality of subtrees. Similarly, while associativity f(X, f(Y, Z)) → f(f(X, Y ), Z) does not compare subtrees, applying it iteratively can reshape trees, destroying information encoded in the tree structure. For instance, consider a regular tree language over constants a, b and binary f such that the string of leaf labels forms a palindrome and every palindrome appears in some tree. This language is defined to contain constants a, b and be closed under the contexts f(a, f(X, a)) and f(b, f(X, b)). A DFTA can detect whether a tree is built from these two contexts and constants. However, if such tree is reshaped to a skewed tree, no DFTA can recognize whether the leaves form a palindrome. Consequently, this language cannot be extended to satisfy associativity while retaining its key properties. Despite this, we only ask whether a language known to be regular satisfies rewrite rules.

3.1 Deciding Consistency

We discuss how to efficiently decide consistency. First, we establish a condition that reduces checking consistency of a TRS with a tree language to checking combinatorial properties of the minimal DFTA recognizing that language (Lemma 6). Next, we discuss the complexity of deciding this combinatorial condition.

To conveniently define the combinatorial condition, we extend the function ̂ δ from trees (i.e., ground terms) to all terms, where terms with variables define state transformations:

Definition 5. Let A be a minimal DFTA and t be a term over variables X1, . . . ,Xk. We define ⃗δA(t) as a function from Qk to Q such that ⃗δA(t)(q1, . . . , qk) is the state assigned to t if in leaves labelled by Xi the DFTA A starts in state qi. Formally, let s1, . . . , sk be trees over F such that ̂ δ(si) = qi. Then, ⃗δA(t)(q1, . . . , qk) = ̂ δ(t[X1 → s1, . . . , Xk → sk]).

Note that in a minimal DFTA every state is reachable, and hence trees s1, . . . , sk as in the above definition exist.

Lemma 6. Let Rbe a TRS over F andAbe aminimal DFTA over F. The TRS R is consistent with L(A) if and only if the functions ⃗δA(l) and ⃗δA(r) coincide, for each rule l → r ∈ R.

It is essential that the TRS and the DFTA are over the same signature F, as otherwise checking consistency is undecidable [Fica and Otop, 2025].

Remark 7. Consider a rule f(X,X) → a, for which the left-hand side defines a non-regular language. Observe that Lemma 6 implies that if f(X,X) → a is consistent with the language of a minimal DFTA A, then for all trees s1, s2 labelled with the same state by A (̂ δ(s1) = ̂ δ(s2)), the tree f(s1, s2) is labeled with the state ̂ δ(a), which is a substantially stronger condition than just f(X, X) → a.

Now, in the remaining part of this section, we discuss the complexity of evaluating the condition from Lemma 6.

For any tuple of states ⃗q ∈ Qk , the value ⃗δA(l)(⃗q) (resp., ⃗δA(r)(⃗q)) can be computed in polynomial time in |l| (resp.,

|r|). However, the number of arguments is equal to the number of variables in terms l, r and hence there may be exponentially many tuples of states to check. Still, Lemma 6 implies that consistency can be checked in coNP:

Proposition 8. Checking consistency of a TRS with a tree language given by a DFTA is in coNP. For every N > 0, consistency is decidable in polynomial time over TRSs with at most N variables, i.e., in every rule l → r, both terms l, r are over {X1, . . . ,XN}.

In particular, the consistency problem is decidable in polynomial time if the TRS is fixed and only the DFTA is the input.

Computing counterexamples. Given a rule l → r ∈ R such that ⃗δA(l) ̸= ⃗δA(r) and q1, . . . , qk witnessing this, i.e., ⃗δA(l)(q1, . . . , qk) ̸= ⃗δA(r)(q1, . . . , qk), we can compute two trees witnessing consistency being violated. Let s1, . . . , sk be trees such that ̂ δ(si) = qi. Consider trees:

• ˆl = l[X1 → s1, . . . ,Xk → sk], and
• ˆ r = r[X1 → s1, . . . , Xk → sk].

Let ql = ̂ δ(ˆl) and qr = ̂ δ(ˆ r). Then, ql ≤ qr. Since A is minimal, there is a context c distinguishing states ql and qr. Thus, for s = c(ˆl) and t = c(ˆ r), exactly one of s, t belongs to L(A). In summary, while s →∗ t in one step, s ∈ L(A) ↔ t ∈ L(A) does not hold. Since we know that s ∈ U ↔ t ∈ U, one of s, t is a counterexample.

In general, the coNP upper bound cannot be improved: Lemma 9. Checking consistency of a rule l → r, where l is a (non-linear) term and r is a ground term with the language of a given DFTA is coNP-hard.

Proof sketch. The proof is by reduction from the tautology problem. The signature consists of binary ∧, ∨, unary ¬ and constants ⊤, ⊥. The rule l encodes an input formula φ, while r is ⊤. Finally, the DFTA views input trees as propositional formulas and evaluates their truth values. Thus, l → ⊤ is consistent exactly when φ is a tautology.

The above lemma holds even for a fixed DFTA. Still, the hardness argument relies on variables occurring multiple times. Therefore, a natural question is what is the complexity of checking consistency of rules l → r, in which both terms are linear. We leave this as an open problem and propose a simple heuristic.

Heuristics for linear rules. We propose a heuristic for linear terms based on the state-counting function, which counts the cardinality of the preimage ⃗δA(l) and ⃗δA(r) with multiplicities. This heuristic does not confirm consistency, but it can identify some rules that violate consistency. This is not a problem as consistency itself overapproximates equivalence. Consequently, any heuristic that overapproximates consistency also overapproximates equivalence, i.e., the heuristic does not err on the negative answers.

Definition 10. For a term t and a DFTA A, we define the state-counting function #A[t] : Q → N as the cardinality of the preimage ⃗δ-1 A [{q}], i.e., #A[t](q) = |{(q1, . . . , qk) | ⃗δA(t)(q1, . . . , qk) = q}|.

Observe that if ⃗δA(l) = ⃗δA(r), then #A[l] = #A[r]. Consequently, checking #A[l] = #A[r] serves as a necessary (but not sufficient) condition for consistency of l → r with L(A) (i.e., it is an underapproximation). This provides a computationally efficient heuristic to filter out inconsistent rules before performing more expensive checks. Furthermore, #A[t] can be efficiently computed for linear terms t, and hence it can be used as a preliminary test even if consistency could be decidable in polynomial but superlinear time.

Lemma 11. The function #A[t] can be computed in time O(|A| · |t|) over linear terms t.

Observe that if one of the functions #A[l] or #A[r] is constant, then #A[l] = #A[r] implies ⃗δA(l) = ⃗δA(r). In particular, for rules l → r such that l is a linear term and r is a ground term, we can decide consistency in linear time.

Corollary 12. The consistency of a rule l → r with L(A) can be performed in time O((|l| + |r|) · |A|) for rules l → r such that l is a linear term and r is a ground term.

3.2 Deciding Positive and Negative Consistency

The notions of positive and negative consistency are dual. Observe that R is positively consistent with L if and only if R is negatively consistent with the complement of L. Therefore, we will focus on positive consistency as the results carry over to negative consistency straightforwardly (note that DFTA can be complemented via swapping accepting and non-accepting states).

First, we present a counterpart of Lemma 6 for positive consistency. For that, we need to define two order relations: one on states and another on states transformations that rank states from the least accepting to the most accepting.

Definition 13. Let A be a DFTA. We define an order relation ≤A on states of A such that q1 ≤A q2 if for all trees t1, t2 such that ̂ δ(t1) = q1 and ̂ δ(t2) = q2, for every context c we have c(t1) ∈ L(A) =⇒ c(t2) ∈ L(A).

Given a DFTA A, the relation ≤A can be computed in O(|A|3 ) by the greatest fixed-point iteration. The algorithm starts with the relation R = Q×Q. It removes pairs (q1, q2) such that q1 ∈ Qacc and q2 /∈ Qacc. Then, iteratively, for every context c of height 1 (which corresponds to a transition), if (c(q1), c(q2)) /∈ R, the pair (q1, q2) is removed from R. The greatest fixed-point is reached after |Q|2 iterations, while each iteration can be performed in O(|A|) by checking all contexts of height 1.

We extend ≤A from states to state transformations:

Definition 14. Let A be a DFTA and k > 0. We define an order relation ≼A on functions from Qk to Q as follows. For all h1, h2 : Qk → Q we have h1 ≼A h2 if and only if h1(⃗q) ≤A h2(⃗q), for all ⃗q ∈ Qk .

Finally, we present the counterpart of Lemma 6 for positive consistency:

Lemma 15. Let R be a TRS over F and A be a minimal DFTA over F. The TRS R is positively consistent with L(A) if and only if ⃗δA(l) ≼A ⃗δA(r), for each rule l → r ∈ R.

Since ≤A can be computed in polynomial time, the condition ⃗δA(l) ≼A ⃗δA(r) can be falsified by finding an appropriate ⃗q and computing q1 = ⃗δA(l)(⃗q), q2 = ⃗δA(r)(⃗q) and finally checking that q1 ≤A q2 does not hold. In consequence, checking positive consistency is in coNP.

Observe that for rules l → r with a ground term r ∈ L, positive consistency and consistency coincide, i.e., l → r is consistent with L if and only if it is positively consistent. If r /∈ L, we can instead take the complement of L and reduce to the previous case. Therefore, for such rules the complexity of checking positive consistency is the same as checking (full) consistency: if r is a ground term, checking consistency of l → r with a regular tree language L is coNP-complete in general, and it is decidable in polynomial time for rules l → r with l being a linear term. When l, r are both linear terms, the complexity of checking consistency of l → r is left open. For positive consistency, we can show that it is coNP-complete. It suffices to show hardness:

Lemma 16. Checking positive consistency of a rule l → r with the language of a given DFTA is coNP-hard for rules l → r such that l, r are linear terms.

Still, we can utilize the heuristic based on #A[t], which was proposed above for consistency. We need to adapt the condition to positive consistency in the following way. We define the cumulative state-counting function Σ#A[t] as Σ#A[t](q) = ∑q≤Aq′ #A[t](q′ ), i.e., it sums the multiplicity of each state q′ that is greater in the ≤A order.

Lemma 17. For terms l, r, if ⃗δA(l) ≼A ⃗δA(r), then #A[l](q) ≤ Σ#A[r](q), for every state q.

Note that having the function #A[r](q2) and the relation ≤A, we can compute Σ#A[t](q) in time O(|Q|2 ) from definition or in O(| <A | · |Q|), where <A is the strict variant of the order ≤A and | <A | is the number of tuples in <A. The latter complexity is achieved by computing the transitive reduction succA [Aho et al., 1972] of <A in O(| <A | · |Q|), i.e., the transitive closure of succA is <A. Then the graph (Q, succA) is sorted topologically in O(|succA| · |Q|) and the summation is performed iteratively over the immediate successors only in O(|succA| · |Q|). Since succA ⊆<A, the whole computation is in O(| <A | · |Q|).

3.3 Membership Queries

Typical implementations of the L∗ algorithm store answers to membership queries in some data structure (e.g. an observation tree) to ensure that each query is unique. We extend this idea to membership queries modulo term rewriting.

For the advice TRS R= (which is fully consistent with the target language), we select a convergent subset R′=. Since the TRS R′= is convergent, every term has a unique normal form.

The algorithm maintains a cache, which is a dictionary mapping each tree's normal form NFR′= (t) to its membership result. Before asking a query for a tree s, the algorithm computes the normal form of s and checks the cache. If present, it fetches the stored answer without querying the oracle. Consistency of R with the target language L implies that if NFR′= (s) = NFR′= (t), then s ∈ L ↔ t ∈ L. Otherwise, if NFR′= (s) is not in the cache, it asks the oracle the membership query and stores NFR′= (s) along with the answer in the cache.

The TRSs R+,R- can be used to infer answers to membership queries as well, but the complexity of inference makes this infeasible [Fica and Otop, 2025].

4 Examples of Advice Rewrite Rules

We present examples of TRS that express interesting properties of tree languages. While these properties originate in algebra, we discuss their relevance to knowledge representation, structured data, and Description Logic (DL) [Nardi et al., 2003].

4.1 Families of TRS

We consider the following types of TRSs: associativity, commutativity, variants of distributivity, and cancellation rules. The applications of these rules are discussed in the context of full consistency. We elaborate on these TRSs below.

Associativity. While we have considered ranked trees, unranked trees with symbols of variable arities are prevalent in structured data. For example, the HTML <body> tag has an arbitrary number of immediate successors, and dictionaries in JSON have arbitrarily many entries. Unranked symbols can be encoded with associative binary symbols; the associativity rule for f: f(X, f(Y, Z)) → f(f(X, Y ), Z) implies that the shape of a tree labelled with f is irrelevant and hence all f symbols can be contracted into a single high-arity symbol. Furthermore, the basic DL operators ⊓ and ⊔ are associative.

Commutativity. Commutativity of f is expressed with the rule f(X, Y ) → f(Y,X). This can be more precisely described as horizontal commutativity, indicating that sibling subtrees can be swapped without changing the tree's value. JSON dictionaries and DL operators ⊓ and ⊔ are (horizontally) commutative. Furthermore, unranked and unordered trees [Boneva and Talbot, 2005] can be modeled with binary operators that are associative and (horizontally) commutative.

Distributivity. The standard distributive properties for binary symbols f, g are: (1) f is left-distributive over g: f(X, g(Y,Z)) → g(f(X, Y ), f(X,Z)), and (2) f is rightdistributive over g: f(g(X, Y ), Z) → g(f(X, Z), f(Y, Z)). DL operators ⊓ and ⊔ are left- and right-distributive one over another, i.e., both ⊓ over ⊔ and ⊔ over ⊓.

Variants of distributivity. Distributivity can be generalized beyond binary symbols. For a binary symbol f and an unary symbol g the rule g(f(X, Y )) → f(g(X), g(Y )) is a variant of distributivity. Similarly, for unary f, g the rule g(f(X)) → f(g(X)) can be considered as a variant of distributivity. This rule states that the relative order of f and g along any root-to-leaf path is irrelevant, i.e., f and g commute along any path. Consequently, variants of distributivity can be regarded as vertical commutativity. Typical examples of vertical commutativity are independent operations such as bold and italic text tags in HTML, which can be applied in any order, or more generally an operator g that is applied to all leaves of the subtree and hence g(f (X, Y )) → f (g(X), g(Y )) holds.

Context cancellation rules. The general form of a context cancellation rule is c(t) → c(X), where c is a context and t is a term. The idempotency property of f expressed with f(f(X)) → f(X) is a context cancellation rule. Similarly, there are various cancellation rules in DL: X ⊓ X → X, X ⊔ X → X and (X ⊓ Y ) ⊔ X → X.

4.2 Experiments

Implementation. We have implemented the L∗ algorithm adapted to bottom-up DFTA. Subsequently, we extended this implementation to handle advice for equivalence queries using our proposed mechanism. Our implementation accepts any set of rewrite rules as input, though our evaluation focuses on the TRS classes mentioned above.

Experiments with associativity. We have evaluated the impact of the advice f(X, f(Y,Z)) → f(f(X, Y ),Z) on the number of equivalence queries on randomly generated automata. To ensure that the language of a randomly generated DFTA satisfies associativity, we generate the DFTA as follows. Let F be a signature consisting of a binary symbol f and constant symbols Σ. The yield of a tree t over F is the sequence of constants Σ in leaves read from left to right. For a regular language K over Σ, we define T K as the tree language consisting of all trees with the yield from K. The membership of a tree in T K does not depend on its shape, which can be expressed by stating that f is associative. Intuitively, a tree t over F can be considered as a tree of height one with a single variable-arity symbol f in the head and constants from Σ as arguments, which is effectively an encoding of a sequence over constant symbols Σ.

Lemma 18. Let L be a regular tree language over a binary symbol f and constants Σ. The rule f(X, f(Y,Z)) → f(f(X, Y ), Z) is consistent with L if and only if L = T K for some regular language K over Σ.

Results for associativity. Based on Lemma 18, we have generated random DFA over the alphabets with 2-5 letters, with 2-16 states and converted each of them to a DFTA. These DFTA are guaranteed to satisfy associativity and their number of states ranged between 20 and 200. The conversion of DFA to DFTA incurs exponential blow-up as DFTA has to process leaves in various orders depending on the shape of the tree. We have removed trivial cases, when the L∗ algorithm finished learning with at most 2 equivalence queries. We have observed reduction of equivalence queries between 29% (from 7 to 5 queries) to 96% (from 49 to 2 queries) with an average reduction of 77%. On average, this corresponds to a reduction from 12.4 to 2.6 equivalence queries.

Results for commutativity. We also evaluated the commutativity advice; however, it did not yield a reduction in the number of equivalence queries. Note that if f(t1, t2) belongs to the language if and only if f(t2, t1) does, then in any candidate automaton computed based on membership queries, the transition function for f is commutative. Commutativity could have been used to reduce the number of membership queries, but not in our framework as f(X, Y ) → f(Y,X) is non-terminating, whereas termination is necessary to compute the normal form.

Results for distributivity. We have generated random DFTA over a binary symbol f and an unary symbol g such that f is distributive over g. The random DFTA had between 5 and 256 states. We have observed reduction of equivalence queries between none to 98% (from 57 to a single equivalence query) with an average reduction of 62%. On average, this corresponds to a reduction from 12.7 to 4.78 equivalence queries.

5 Generating Advice

While we have discussed how advice provided via a TRS can facilitate the learning of an unknown tree language, this section addresses the converse: synthesis of rewrite rules consistent with a given regular tree language. Given a tree automaton recognizing a tree language, the goal is to find a TRS consistent with that language. A synthesized TRS can serve as an explanation of the regular tree language, capturing its key properties through concise rewrite rules. We consider the automaton to be given rather than learned, as we show that even this easier variant of the problem is already difficult.

We begin by observing that the transition function of a DFTA A can be viewed as a ground term rewriting system. The resulting TRS RA completely characterizes the target language, i.e., if RA is used as the advice TRS, the language of A can be learned with a single equivalence query.

Fact 19. Given a DFTA A we can compute a ground TRS RA that completely characterizes L(A).

While RA demonstrates that the number of equivalence queries can be reduced to one, it is not practically relevant, as it is derived directly from the automaton being learned. Such detailed advice essentially describes the automaton itself, rendering the learning process redundant. Furthermore, this TRS is not structurally insightful as it does not explain the tree language any better than the automaton itself. Therefore, we are interested in synthesizing non-ground rewrite rules, where the left-hand side is a non-ground term, that are consistent with a given tree language and possibly small.

Formally, we study the following problem:

Definition 20 (Synthesis of TRS). Given a DFTA A over a signature F, the Rule Synthesis problem is to find a nonground rewrite rule l → r, where l, r ∈ T (F,X), such that (1) l → r is consistent with L(A), (2) the value |l| + |r| is minimal among rules satisfying (1).

However, the hardness of the Rule Synthesis problem emerges already in the case of unary and constant symbols.

The unary case. Consider a signature Funary consisting of unary symbols a, b, c and a constant #. Let A be a DFTA over Funary. Observe that a ground term t over Funary corresponds to a state of A with ⃗δA(t) = ̂ δ(t), while a non-ground term s corresponds to a unary state transformation, i.e., ⃗δA(s) is a function from Q to Q.

The rule l → r is consistent with L(A) if and only if the transformation induced by l is a constant function equal to ̂ δ(r). If we view the unary symbols in l (read from bottom to top) as a word wl over {a, b, c}, then wl is a synchronizing word in A regarded as a DFA.

While it can be decided in polynomial time whether a DFA has a synchronizing word [ ˇCern`y, 1964], finding the shortest synchronizing words in DFA is NP-complete [Eppstein, 1990] and it is even NP-hard to approximate it within a constant factor [Berlinkov, 2014]. The hardness of approximation carries directly from DFA to DFTA.

Lemma 21. If P ̸= NP, there is no polynomial-time algorithm that, given a DFTA A over Funary, approximates within a constant ratio the size of the shortest rewrite rule l → r such that r is a ground term and l is a non-ground term, and l → r is consistent with L(A).

On the positive side, if we drop the minimality condition and restrict to contexts, the existence of such a rule is decidable in polynomial time similarly to [ ˇCern`y, 1964]:

Lemma 22. It is decidable in polynomial time, given a DFTA A over F, whether there exists a rule l → r such that (1) l is a context and r is a ground term, and (2) l → r is consistent with L(A).

Not only is the complexity of rule synthesis challenging, but there is also no single clear objective. While non-ground rules l → r are more meaningful than ground rules, several questions remain regarding the objectives for synthesis:

• Should both terms l and r be non-ground, or only l?
• Should l be permitted to contain constants?
• Should l be restricted to linear terms, or allowed to contain repeated variables (non-linear terms)?

Investigating these variations is essential for the design of future synthesis algorithms. We leave the comprehensive synthesis of rewrite rules as an open problem for future work.

6 Conclusions

We have presented a method that leverages structural knowledge of a target tree language to significantly reduce the number of equivalence queries required during active learning. In contrast to the word-automata setting, the branching structure of trees means that checking consistency of a TRS with a tree automaton, which is the core of our method, entails a higher computational complexity. Thus, a key direction for our future work involves developing further heuristics and investigating specific subclasses of TRSs to reduce the computational cost of consistency checking. While we have established several complexity bounds, the complexity of checking consistency of linear rules remains an open problem.

Beyond theoretical refinements, we aim to explore broader applications of this framework. Building on successful experiments with the associativity rewrite rule on synthetic data, we believe the framework is well-suited for more complex domains. Specifically, since our advice mechanism can express various properties of Description Logics (DL), applying active tree automaton learning with advice to learn DL terminologies represents a promising research path.

Finally, while we have only briefly explored the synthesis of consistent TRSs, we consider this a promising frontier for future research. Identifying the right objectives for such synthesis will be a prerequisite for developing robust automated advice-generation tools.

Acknowledgments

This work was supported by the National Science Centre (NCN), Poland under grant 2024/53/B/ST6/01620. We thank the anonymous reviewers for their valuable feedback.