Learning Weighted Automata over Number Rings, Concretely and Categorically

Basic Information

• Paper ID: 2504.16596
• Title: Learning Weighted Automata over Number Rings, Concretely and Categorically
• Authors: Quentin Aristote, Sam van Gool, Daniela Petrişan, Mahsa Shirmohammadi
• Classification: cs.FL (Formal Languages and Automata Theory)
• Publication Date: April 23, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2504.16596

Abstract

This paper develops a general active learning problem reduction procedure. The approach is inspired by recent work by Buna-Marginean et al. (2024), which polynomially reduces the exact learning problem for weighted automata over integers to the learning problem for weighted automata over rationals. The procedure improves the efficiency of categorical automata learning algorithms and raises new questions about implementation complexity when instantiated in concrete categories. As a second major contribution, the authors address these complexity questions in the concrete setting of learning weighted automata over number rings (rings of integers in algebraic number fields). Assuming a complete representation of the number ring OK, they obtain an exact learning algorithm for OK-weighted automata with polynomial time complexity in the target automaton size, the logarithm of the longest counterexample length, the degree of the number field, and the logarithm of the discriminant. The algorithm produces automata with at most one more state than the minimal automaton, and it is proven that doing better requires solving the principal ideal problem, for which the best known algorithm is quantum polynomial time.

Research Background and Motivation

Problem Background

1. Classical Automata Learning: Angluin's L* algorithm efficiently learns deterministic finite-state automata in the Minimally Adequate Teacher (MAT) framework, a classical result in computational learning theory.
2. Challenges in Weighted Automata Learning: Extending learning algorithms to more expressive models (such as weighted automata) presents challenges, particularly when weights lie in rings rather than fields.
3. Limitations of Existing Approaches:
   • Polynomial time learning algorithms exist for weighted automata over fields
   • For weighted automata over general rings, existing methods either have excessive complexity or limited applicability
   • Categorical approaches, while general, may lead to exponential complexity in concrete instantiations

Research Motivation

1. Theoretical Requirement: Need for a framework that maintains the generality of categorical methods while achieving polynomial complexity in concrete cases
2. Practical Applications: Number rings have important applications in cryptography; efficient learning of weighted automata over them has practical value
3. Theoretical Boundaries: Exploring theoretical limits of weighted automata minimization, particularly generalizations of the Fatou property

Core Contributions

1. General Reduction Algorithm: Proposes Algorithm 3, a general reduction procedure within the categorical framework that reduces one class of learning problems to another more tractable class
2. Concrete Algorithm for Number Rings: Develops Algorithm 4, a polynomial time learning algorithm specifically for weighted automata over number rings OK
3. Near-Optimality Results: Proves that the algorithm produces automata with at most one more state than the minimal automaton (near-minimality)
4. Theoretical Complexity Bounds: Proves that obtaining completely minimal automata is equivalent to solving the principal ideal problem (PIP-hard), establishing theoretical lower bounds
5. Generalization of Fatou Property: Proves that Dedekind domains are "almost strongly Fatou rings," generalizing the classical Fatou property

Methodology Details

Task Definition

Input: An unknown OK-weighted language L: Σ* → OK (accessed via oracle) Output: An OK-weighted automaton computing L Constraint: Algorithm complexity is polynomial in the target automaton size, logarithm of the longest counterexample length, degree of the number field, and logarithm of the discriminant

Core Technical Framework

1. Categorical Foundations

The paper adopts a functor perspective, viewing automata as functors A: I → C, where:

• I is the free category generated by alphabet Σ
• C is the output category (e.g., module category ModR)

2. General Reduction Algorithm (Algorithm 3)

Algorithm Idea:
1. Learn automaton in "tractable" category D
2. Establish connection via functor F: C → D
3. Use right adjoint G: D → C to pull back results to target category C

Key Assumption (Assumption 12):

• F preserves certain morphism classes
• F has a right adjoint G
• Unit and counit morphisms have specific properties

3. Concrete Implementation over Number Rings (Algorithm 4)

Step 1: Backward Conjugation

Compute basis B of backward space of automaton A
Conjugate A by matrix B to obtain A'

Step 2: Forward Module Generation

Call Algorithm 5 to compute generating set of forward OK-module of A'
Use two-phase strategy:
- Phase 1: Find words increasing rank in K
- Phase 2: Complete module generation in OK

Step 3: Pseudo-basis Computation

Compute pseudo-basis from generating set using pseudo-Hermite Normal Form (pseudo-HNF)
Pseudo-basis form: {(ai, vi) | 1 ≤ i ≤ ℓ}, where ai are fractional ideals

Step 4: Almost-Minimal Generating Set

Convert pseudo-basis to generating set of size at most ℓ+1 via Algorithm 6
Use ideal factor refinement and Chinese Remainder Theorem

Technical Innovations

1. Two-Phase Generation Strategy: First determine rank in field K, then complete module structure in ring OK, avoiding exponential complexity
2. Pseudo-basis Technique: Leverages structure theory of Dedekind domains to handle non-principal ideal domains
3. Integration of Categorical and Concrete Algorithms: Concretizes abstract categorical framework into implementable polynomial algorithms

Experimental Setup

Theoretical Verification

The paper is primarily theoretical work, verified through:

1. Complexity Analysis: Detailed analysis of time complexity for Algorithm 4 and Algorithm 5
2. Correctness Proofs: Theorem 18 proves correctness of the general algorithm
3. Concrete Examples: Provides specific examples (e.g., Example 1) illustrating the case over Zi√5

Complexity Bounds

Theorem 2: Given a complete representation of OK, exact learning of OK-weighted automata is solvable in polynomial time in:

• Target automaton size
• Logarithm of longest counterexample length
• Degree d of the number field
• Logarithm of discriminant ΔK

Experimental Results

Main Theoretical Results

1. Near-Optimality (Proposition 10): For a Dedekind domain R, if L is an R-weighted language of rank n, there exists an R-weighted automaton computing L with at most n+1 states
2. Complexity Lower Bound (Proposition 26): Determining whether an OK-weighted automaton is state-minimal is PIP-hard
3. Fatou Property Generalization (Corollary 16): Dedekind domains are almost strongly Fatou rings

Concrete Example Analysis

Example 1: In the number ring R = Zi√5:

• Constructs a 3-state R-weighted automaton
• An equivalent 2-state K-weighted automaton exists (K = Q(i√5))
• Illustrates that strong Fatou property does not always hold, but almost strong Fatou property does

Related Work

Classical Automata Learning

• Angluin's L* algorithm: Polynomial learning of deterministic finite automata
• Beimel et al.: Learning algorithms for weighted automata over fields

Weighted Automata over Rings

• van Heerdt et al.: Learning over principal ideal domains, but without complexity bounds
• Buna-Marginean et al.: Reduction from Z to Q, direct inspiration for this work

Categorical Approaches

• Colcombet-Petrişan: Functor methods for automata minimization
• Urbat-Schröder et al.: Algebraic approaches to learning

Conclusions and Discussion

Main Conclusions

1. Develops the first polynomial time algorithm for learning weighted automata over number rings
2. Proves the hardness of obtaining completely minimal automata (PIP-hard)
3. Establishes a bridge between categorical theory and concrete algorithms

Limitations

1. Representation Requirements: Requires a "complete representation" of number ring OK, which may be difficult to obtain in practice
2. Near-Optimality: The algorithm may produce automata with one more state than minimal
3. Specific Structure: Methods are specialized for Dedekind domains; generalization to arbitrary rings is unclear

Future Directions

1. Other Ring Classes: Investigate generalizations to non-Dedekind domains
2. Practical Implementation: Develop concrete software implementations and experimental validation
3. Application Exploration: Concrete applications in cryptography and related fields

In-Depth Evaluation

Strengths

1. Theoretical Depth: Skillfully combines categorical theory, algebraic number theory, and computational complexity
2. Technical Innovation: Creative use of two-phase learning strategy and pseudo-basis techniques
3. Completeness: Provides both algorithms and lower bounds, offering a complete picture of the problem
4. Rigor: Mathematically rigorous proofs and detailed complexity analysis

Weaknesses

1. Practical Applicability: Lacks concrete implementation and experimental validation
2. Readability: Categorical portions may be difficult for non-specialists
3. Scope of Applicability: Method applicability is limited to specific algebraic structures

Impact

1. Theoretical Contribution: Makes important contributions to weighted automata learning theory
2. Methodology: Demonstrates how to concretize abstract categorical methods
3. Interdisciplinary: Connects automata theory, algebraic number theory, and computational complexity

Applicable Scenarios

1. Cryptography: Applications of number rings in lattice-based cryptography
2. Symbolic Computation: Computational problems over algebraic number fields
3. Theoretical Research: Provides foundation for further automata learning research

Additional Technical Details

Representation of Number Rings

The paper requires a "complete representation" of OK including:

• Integral basis Ω = {ω1,...,ωd}
• Primitive element θ and its minimal polynomial
• Complexity measure CK = d⁴(log d + log ΔK)

Algorithm Complexity

Key complexity bounds derive from:

• Pseudo-HNF computation: Polynomial time (Biasse-Fieker-Hofmann)
• Strictly increasing chain length: Bounded by log(N(d)) via Lemma 24
• Ideal operations: Polynomial time in CK

This paper makes important theoretical contributions to theoretical computer science, particularly at the intersection of automata learning and algebraic computation. While practical applicability remains to be verified, its theoretical value and methodological significance are substantial.