PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Canonical Register Automata over Ordered Data Domains

Yong Li, Qiyi Tang, Di-De Yen

arXiv:2608.18765v1cs.CLcs.LG

TL;DR

Learning deterministic register automata over ordered data domains is complicated by differences between dense and non-dense domains. This paper unifies both cases in a polynomial-query framework and shows that minimization over integers is decidable.

  • Problem

    Learning deterministic register automata over ordered domains requires addressing additional complications introduced by ordered comparisons on non-dense domains.

  • Method

    The paper develops an active learning framework using membership, equivalence, and memorability queries for DRAs over ordered data domains.

  • Results

    The unified framework supports polynomially many queries and establishes decidable minimization for DRAs over non-dense domains, including the integers.

  • Takeaways & Limitations

    The results extend minimization decidability from dense to non-dense ordered domains and provide a common learning framework for both.

  • Takeaways & Limitations

    A full learning algorithm using only membership and equivalence queries remains future work and would require exponentially many membership queries.

Abstract

from arXiv · show

Register automata are finite automata equipped with memory that recognize data languages over infinite alphabets. In this work, we investigate active learning algorithms for deterministic register automata (DRAs) over ordered data domains--covering both dense domains, such as the rationals, and non-dense domains such as the integers. We show that the active learning problem for DRAs over both dense and non-dense ordered domains can be treated within a single unified framework. More specifically, we develop and implement a polynomial-time active learning procedure for DRAs over ordered domains, using oracles for membership, equivalence and memorability queries. The memorability queries were originally introduced for learning DRAs over domains with identity tests. Our unified framework also leads to a new consequence: minimization of DRAs over the non-dense ordered domain of integers is decidable, extending a result previously known only for dense domains. Finally, we give improved complexity bounds of several decision problems for DRAs over ordered domains that are closely related to the queries used in active learning.

1 Introduction

The paper develops a unified active-learning framework for deterministic register automata with ordered comparisons over both dense and non-dense data domains. It also extends minimization decidability to integers and establishes complexity results for related decision problems.

  • Motivation: DRAs with ordered comparisons target ordering-based properties that identity-test automata cannot capture, such as checking whether an input sequence is sorted.Ordered comparisons test equality and whether inputs are greater or smaller than stored register values.
  • Contributions: Minimal DRAs over Q and minimal DRAs over Z recognizing the same integer-restricted language are structurally equivalent, extending dense-domain minimization results to non-dense domains.The paper also establishes decidability of configuration reachability over Z.
  • Contributions: The active-learning algorithm applies uniformly to dense and non-dense ordered domains and uses polynomially many membership, equivalence, and memorability queries.Memorability queries identify which symbols must be stored in registers.
  • Contributions: The implemented learner uses S-consistency under canonical renamings and stored-value subsets, with counterexample handling that updates symbolic transitions rather than only separating states.Its effectiveness is demonstrated on data languages and randomly generated DRAs.
  • Contributions: PSPACE-completeness holds for language inclusion and intersection non-emptiness over equality and ordered domains, while dense ordered domains additionally have PSPACE upper bounds for configuration equivalence, language equivalence, and memorability.The memorability upper bounds improve previous known bounds.

2 Preliminaries

The preliminaries define ordered data domains, data-word types, and register automata, including determinism and configurations. They also explain minimality issues and introduce well-typed DRAs to ensure minimal representatives exist.

  • The paper treats Q and R as dense ordered domains, while Z is non-dense, and considers alphabets from {R, Q, Z} with either < or =.
  • Data languages are invariant under the equivalence relation induced by equal word lengths and corresponding pairwise relations between symbols.
  • Register automata extend finite-state automata to infinite alphabets; a k-RA uses typed transitions, and a DRA assigns a unique target and register-update set for each source-state and type pair.
  • A minimal RA need not exist, so well-typeness is introduced to guarantee a minimal well-typed DRA for every DRA-recognizable language without reducing expressive power.

3 DRAs over Non-Dense Ordered Domains

This section establishes the Myhill–Nerode foundation for DRAs over ordered domains and resolves non-dense-domain problems including configuration reachability and minimization. It also shows that language equivalence and minimization over dense and non-dense domains fit a unified framework.

  • Memorability: Memorability captures the symbols that determine future membership, with non-dense domains requiring same-type words because nearby replacement values may not exist.In dense domains, a memorable symbol can be tested by replacing it with a nearby value; this direct replacement can fail over non-dense domains.
  • Myhill–Nerode characterization: The Myhill–Nerode theorem characterizes DRA-recognizable languages by finite-index equivalence and yields a unique minimal canonical DRA up to isomorphism.The canonical automaton may generally be infinite or nondeterministic, but is exactly the minimal DRA for DRA-recognizable languages.
  • Non-dense-domain decision problems: Configuration reachability for DRAs over (Z, <) is decidable, resolving an open problem caused by the failure of density-based transition arguments.Over non-dense domains, whether a transition can be enabled may depend on the specific stored values and available gaps.
  • Non-dense-domain decision problems: Minimization for DRAs over (Z, <) is decidable as an immediate consequence of configuration reachability decidability.The section also relates minimization to residual-language equivalence and configuration reachability in a product automaton.

4 Active Learning of DRAs

The section presents a polynomial-query active-learning algorithm for DRAs over ordered domains using membership, equivalence, and memorability queries. It unifies dense and non-dense domains by reducing learning over (Z, <) to learning over (Q, <), and derives related complexity results.

  • Learning framework: The learner populates an observation table with membership queries, constructs a conjectured DRA, and refines it with counterexamples until an equivalence query is answered “Yes”.The table records prefixes, extensions, suffixes, memorable words, and membership classifications.
  • Ordered domains: Learning over (Z, <) reduces to learning over the dense domain (Q, <), while dense-order mappings reduce inequivalence testing to finding one distinguishing suffix.For words with order-equivalent memorable parts, an order-preserving bijection and a single suffix suffice to witness inequivalence.
  • Learning framework: Memorability queries return memL(u), overcoming the absence of known polynomial-time learning algorithms for data languages with equality tests alone.The proposed learner uses membership, equivalence, and memorability queries.
  • Correctness and complexity: The observation-table construction yields a minimal DRA when its prefixes are exactly the representatives of the Nerode equivalence classes.Counterexamples add distinguishing suffixes; each counterexample of length |w| requires at most |w| refinement iterations.
  • Correctness and complexity: Algorithm 2 terminates, returns a DRA isomorphic to the target, uses at most m × (n −1) equivalence queries and m memorability queries, and requires O(d × m × n + m3 × n3) additional complexity.These bounds are stated directly for the algorithm’s parameters m, n, and d.
  • Decision problems: For dense ordered domains, intersection non-emptiness and language inclusion are PSPACE-complete, while configuration and language equivalence and memorability are in PSPACE.The memorability upper bound improves on the previously established NEXPTIME upper bound.

5 Conclusion and Discussion

The paper unifies the treatment of dense and non-dense ordered domains, establishing decidable minimization for non-dense domains and implementing active learning with membership, equivalence, and memorability queries. It also identifies future work on removing memorability queries and extending the model to action-labelled data words.

  • Contributions: DRAs over dense and non-dense ordered domains can be treated within a unified minimization framework.This framework yields decidability for minimization over non-dense domains, resolving a previously open question.
  • Contributions: The implemented active learning procedure uses membership, equivalence, and memorability queries, and experiments show it complements existing approaches.
  • Future work: A future algorithm using only membership and equivalence queries could use abstract suffixes, but checking consistency and counterexamples becomes more involved.The approach would require an exponential number of membership queries because all concrete suffixes over Du,v must be enumerated.
  • Model scope: The paper’s direct-over-D model is not equivalent to RaLib’s A × D model because action labels can distinguish inputs with the same data value.An extension to A × D would preserve the finite action sequence while comparisons are handled over data values.

A Missing Proofs of Section 3 · A.1 Proof of Theorem 7

The section proves that configuration reachability for DRAs over the ordered integer domain (Z, <) is decidable. The proof reduces reachability to finitely many bounded-length runs by establishing range compression and a pumping-style shortening property.

  • A Missing Proofs of Section 3: Configuration reachability for DRAs over (Z, <) is decidable.This is Theorem 7.
  • A.1 Proof of Theorem 7: The proof establishes a range bound: values in a run can be bounded between min(v) − 3κ · n and max(v) + 3κ · n.This bound follows from repeatedly applying an order-preserving squeezing transformation at most κ · n times.
  • A.1 Proof of Theorem 7: If a run exceeds len(A, v), a shorter valid run exists, yielding the length bound required for decidability.The stated threshold is (Σ_i=0^κ(max(v) − min(v) + 2)^i) · |Q| ≡ len(A, v).
  • A.1 Proof of Theorem 7: Reachability can therefore be checked over finitely many configurations whose register values lie in {min(v) − len(A, v), …, max(v) + len(A, v)}.Only runs of length at most len(A, v) need examination, so the verification process is decidable.
  • A.1 Proof of Theorem 7: Lemma 20 supplies the sequence-combinatorial bound used to find two compatible subruns when ℓ > (d + 2)^θ.The lemma applies to pairwise distinct strictly increasing sequences of a common length θ.

A.2 Minimization Algorithm for DRAs

Algorithm 3 minimizes DRAs by merging states with equivalent representative words, then adjusting outgoing transitions using memorability information to obtain data-minimality. Its effectiveness follows from decidability of representative, memorability, and word-equivalence problems, which reduce to configuration reachability.

  • Algorithm 3: Algorithm 3 computes a representative word for each state, merges states with word-equivalent representatives, and adjusts outgoing transitions using memL(wq) to achieve data-minimality.After merging, the automaton is state-minimal; the final memorability-based adjustment targets data-minimality.
  • Required decision problems: The minimization procedure relies on decidability of the representative, memorability, and word-equivalence problems.These problems respectively compute state representatives, determine memL(u), and test whether two words are equivalent for L.
  • Required decision problems: Representative computation is decidable when configuration reachability is decidable and witness words can be effectively extracted.The representative problem asks for a word wq reaching state q from the initial configuration whenever such a representative exists.
  • Required decision problems: The word-equivalence problem, and therefore DRA minimization, is decidable because equivalence reduces to configuration reachability.DRA equivalence from configurations reduces to reachability of a product automaton, which can be translated into a well-typed DRA.

B More Examples on the Learning Algorithm

Example 23 traces how the learning algorithm processes counterexample 4·5·4·5, using register mappings and membership queries to identify a returned word and refine the conjecture. The returned word 0 is added to S, producing table T2 and conjecture H2 before a further refinement.

  • Counterexample processing: The teacher’s counterexample w = 4·5·4·5 satisfies w ∈L but w /∈L(H1), triggering iterative decomposition and query processing.The example begins with u = ε, r = ε, and mq = +.
  • Counterexample processing: The first two iterations apply register mappings to transformed suffixes and receive positive membership-query answers for 0·1·0·1.Both iterations update the processed prefixes and residual words while the mappings remain identities.
  • Counterexample processing: In the final iteration, the algorithm computes v = 0 and receives MQ(0·0) = −, so 0 is added to S.Here M(0·1·0) = 1 while M(0) = 0, making σ2 map the transformed suffix to 0.
  • Conjecture refinement: Closing the updated table yields T2 and conjecture DRA H2, which is then refined with counterexample 1·0·1·2·1·2.The resulting final table is indicated but not shown in the supplied passage.

C More Details on Learning DRAs over Non-dense Domains

DRAs over the non-dense ordered domain (Z, <) can be learned using the dense-domain learner for (Q, <) by adding an interface to the teacher. The interface translates membership, memorability, and equivalence queries between the domains, yielding a correct DRA for the target language over Z.

  • Interface to the dense-domain learner: An interface connects the dense-domain DRA learner with a teacher answering membership, memorability, and equivalence queries over Z.The target language over Z is related to a corresponding language over Q.
  • Query translation: Membership queries for words over Q are answered by applying a bijective order-preserving mapping σ to words over Z and querying the mapped word.Because u ∼R σ(u), the original and mapped words have the same membership in the target language over Q.
  • Query translation: Memorability queries are translated by querying Mem(σ(u)) over Z and returning σ−1(Mem(σ(u))) over Q.The equivalence u ∼R σ(u) preserves the positions of memorable words across the dense domains.
  • Equivalence queries: Equivalence queries on a conjectured DRA H over Q are resolved by converting it to H′ over Q, querying EQ(H′), and returning any counterexample to the learner.A “Yes” answer produces the corresponding DRA H′ over Z; otherwise, the counterexample is also valid over Q.
  • Correctness: The learning algorithm outputs a correct DRA for the target language LZ by Theorem 9.This correctness result applies to the interface-based learning procedure for the non-dense domain.

D Missing Proofs of Section 4.1

The section supplies missing proofs establishing key dense-domain lemmas, the behavior of S-consistency, and the termination and complexity guarantees of the learning algorithm. Together, these arguments justify that Algorithm 2 reconstructs the canonical minimal DRA with the stated query bounds.

  • Dense-domain lemmas: For dense alphabets, Lemma 11 characterizes inequivalence of u1 and u2 via an order-preserving bijection and a distinguishing suffix w.The characterization requires memL(u1) ∼R memL(u2) and relates σ(u1) · w and u2 · w having different membership outcomes.
  • Dense-domain lemmas: Lemma 24 shows that bijective order-preserving mappings agreeing on memL(u) preserve every continuation’s membership, yielding Lemma 12.Lemma 12 therefore reduces inequivalence under a specified mapping σ to the existence of a suffix w that distinguishes σ(u1) from u2.
  • S-consistency: S-consistency is not an equivalence relation: it is neither symmetric nor transitive, although failure of S-consistency implies language inequivalence and persists when S grows.The supplied example witnesses both non-symmetry and non-transitivity during learning.
  • Algorithm 1: Algorithm 1 terminates within |w| iterations and returns a suffix v that makes an extension ub inconsistent with a previously S-consistent word u′.The proof uses Lemma 27 to align Algorithm 1’s state sequence with the counterexample run and shows that membership results must flip before the final state.
  • Algorithm 2: Algorithm 2 returns a DRA isomorphic to the canonical minimal DRA, uses at most m × (n −1) equivalence queries and m memorability queries, and requires O(d × m × n + m3 × n3)Each transition can be corrected at most n −1 times, while memorability queries are needed only for outgoing transitions and newly added one-letter extensions.

E Preliminary Experiments

The proposed active learning algorithm was implemented in Python and evaluated on paper examples and randomly generated DRAs. Experiments on the Ln family showed polynomial query growth, while comparisons with RaLib highlighted different query trade-offs and the correctness benefit of exact equivalence checking.

  • Experimental setup: The Python implementation was evaluated on all paper examples and randomly generated DRAs, including Ln for n = 1, . . . , 25.Experiments ran on Ubuntu 24.04 LTS with an Intel i7-11800H CPU and 16 GB of RAM.
  • Query complexity: All query types grow polynomially with target-DRA size, with MQs growing fastest, followed by EQs and Mem queries.The target DRAs have 2n states and 6n−6 transitions; the ordering matches Theorem 16.
  • Evaluation of RaLib and our approach: RaLib uses fewer TQs, whereas our approach uses individual-word MQs, making its runtime MQ-dominated while RaLib spends more time on EQs.Our approach nevertheless scales predictably with target-model size, with linear growth in memorability queries.
  • Evaluation of RaLib and our approach: Exact equivalence checking ensures correctness, unlike RaLib’s approximate checking, but requires more EQs as model size increases.The well-typed register model also appears to enable fast equivalence checking in practice.
  • Additional benchmarks: Register benchmarks from RaLib were adapted by combining each EFSM input transition with its corresponding output transition and adding transitions for unsupported multiple parameters.The source text notes that no established EFSM-to-register-automata translation is known.

F Additional Experiments

Additional experiments evaluate learning on structured language families and randomly generated DRAs. Membership-query resolution dominates runtime, while membership queries grow fastest among query types in the random-DRA experiments.

  • The Family of Languages Ln: Membership-query resolution dominates the total runtime of the learning procedure.Reported total time includes teacher-solving time for equivalence, membership, and memorability queries.
  • The Language Lmid: Lmid over (R, <) requires 2 EQs, 72 MQs, and 11 memorability queries.Its minimal well-typed DRA has 5 states and 11 transitions.
  • The Language Lrep of Section 4.1: Learning the minimal well-typed DRA for Lrep requires 3 EQs, 156 MQs, and 14 memorability queries.The automaton has 6 states and 14 transitions.
  • Randomly Generated DRAs: Random experiments used 50 minimal well-typed DRAs for each size from 5 through 50.The study reports average EQ, MQ, memorability-query counts, and learning time.
  • Randomly Generated DRAs: Membership queries grow fastest, followed by equivalence and memorability queries, matching Theorem 16.This trend is reported for the random-DRA experiments and compared with the family Ln results.

G Missing Proofs of Section 4.2

This section establishes PSPACE-completeness of language intersection non-emptiness and inclusion for DRAs over equality and ordered domains, using a polynomial-space product-automaton procedure and a Turing-machine reduction. It also places configuration equivalence, language equivalence, and memorability for dense ordered domains in PSPACE.

  • Language intersection and inclusion: PSPACE: intersection non-emptiness is decided by exploring the product register automaton while storing only a counter and the current configuration.A shortest accepting run is bounded by |Q1| · |Q2| · (k1 + k2)!, yielding polynomial space; Savitch’s theorem gives PSPACE membership.
  • Language intersection and inclusion: PSPACE-complete: language intersection non-emptiness for DRAs over (Σ, =) and (Σ, <), and consequently language inclusion.Inclusion is reduced to intersection emptiness by complementing the second DRA.
  • Language intersection and inclusion: PSPACE-hardness follows from linear-bounded deterministic Turing-machine acceptance via polynomial-size DRAs encoding tape contents with distinct register values.The constructed DRAs use identity tests only, and synchronized accepted words correspond to accepting machine computations.
  • Dense-domain decision problems: PSPACE: configuration equivalence and language equivalence for DRAs over dense ordered domains (Σ, <).Configuration equivalence is used to establish the PSPACE upper bound for memorability.
  • Dense-domain decision problems: PSPACE: the memorability problem for DRAs over dense ordered domains (Σ, <).Memorability is characterized using L-distinguishing extensions and mappings, then decided through configuration equivalence.
Loading 2608.18765v1…