Minimization of Graph Weighted Models over Circular Strings

Guillaume RabusseauFoSSaCS 2018 · OpenReview

Abstract

Graph weighted models (GWMs) have recently been proposed as a natural generalization of weighted automata over strings, trees and 2-dimensional words to arbitrary families of labeled graphs (and hypergraphs). In this paper, we propose polynomial time algorithms for minimizing and deciding the equivalence of GWMs defined over the family of circular strings on a finite alphabet ($GWM^c$s). The study of $GWM^c$s is particularly relevant since circular strings can be seen as the simplest family of graphs with cycles. Despite the simplicity of this family and of the corresponding computational model, the minimization problem is considerably more challenging than in the case of weighted automata over strings and trees: while linear algebra tools are overall sufficient to tackle the minimization problem for classical weighted automata (defined over a field), the minimization of $GWM^c$s involves fundamental notions from the theory of finite dimensional algebra. We posit that the properties of $GWM^c$s unraveled in this paper will prove useful for the study of GWMs defined over richer families of graphs.

Introduction: From Strings to Graphs

Weighted Finite Automata (WFA) are fundamental tools for modeling functions over sequential data like strings and trees. However, as data structures evolve toward more complex graph-based representations, standard WFA reach their theoretical limits. Graph Weighted Models (GWMs) were recently introduced to bridge this gap, generalizing WFA to arbitrary labeled graphs.

A critical hurdle in the adoption of GWMs is the minimization problem: finding the smallest possible model that computes a specific function. While this is a solved problem for strings using basic linear algebra, the introduction of cycles—even in the simplest case of circular strings—introduces significant mathematical complexity.

The Challenge of Circularity

Circular strings are strings where the final symbol connects back to the first, forming a single cycle. In a standard WFA, a string is evaluated via a vector-matrix-vector product ($\alpha^\top M^x \omega$). In a circular GWM ($GWM^c$), the evaluation relies on the trace operator ($\text{Tr}(M^x)$).

A comparison between a linear string (left) and a circular string (right), representing the transition from standard WFA to circular GWMs.

This shift from vectors to traces means that two minimal models are not necessarily related by a simple change of basis. This departure from classical automata theory necessitates a move from linear algebra to the more sophisticated realm of finite-dimensional associative algebras.

Methodology: Algebraic Decomposition

The paper's core contribution is a polynomial-time pipeline for minimization and equivalence testing, built on several key algebraic steps:

  1. Wedderburn-Malcev Decomposition: The author uses the Wedderburn-Malcev Theorem to decompose the matrix algebra generated by the model. This separates the "semi-simple" part of the algebra from the "radical"—a collection of nilpotent elements that act as algebraic noise in the trace calculation.
  2. Semi-simplification: It is proven that any function recognizable by a $GWM^c$ can be computed by a "semi-simple" version of that model. This process effectively filters out the radical components that do not contribute to the final output.
  3. Kernel Projection: Once the model is reduced to its semi-simple form, minimization is achieved by projecting the matrices onto the orthogonal complement of a common kernel.
  4. Algorithmic Implementation: By integrating existing algebraic algorithms (such as those by Bremner or de Graaf), the author demonstrates that these steps can be executed in polynomial time.

Key Insights and Results

The research establishes a formal link between the minimality of a graph model and the semi-simplicity of the algebra it generates. The "aha moment" of the work is the realization that the lack of a unique minimal form in circular models is caused by the "radical" of the algebra. By enforcing semi-simplicity, the author restores the "unique up to a change of basis" property, enabling robust minimization and equivalence testing.

Key Results include: * Equivalence Algorithm: A polynomial-time procedure to determine if two $GWM^c$s compute the same function. * Minimization Algorithm: A polynomial-time procedure to find the $GWM^c$ with the smallest possible dimension for a given function.

Conclusion and Future Directions

This work provides the first polynomial-time algorithms for $GWM^c$ minimization, proving that cycles fundamentally change the underlying mathematics of automata. While currently limited to fields of characteristic 0 and circular strings, these findings lay the groundwork for extending GWM theory to more complex graphs and hypergraphs. Future research will likely explore approximate minimization for machine learning applications and the extension of these algebraic tools to finite fields and semi-rings.

Summary updated

Abstract

Graph weighted models (GWMs) have recently been proposed as a natural generalization of weighted automata over strings, trees and 2-dimensional words to arbitrary families of labeled graphs (and hypergraphs). In this paper, we propose polynomial time algorithms for minimizing and deciding the equivalence of GWMs defined over the family of circular strings on a finite alphabet (GWM $$^\mathrm{c}$$ s). The study of GWM $$^\mathrm{c}$$ s is particularly relevant since circular strings can be seen as the simplest family of graphs with cycles. Despite the simplicity of this family and of the corresponding computational model, the minimization problem is considerably more challenging than in the case of weighted automata over strings and trees: while linear algebra tools are overall sufficient to tackle the minimization problem for classical weighted automata (defined over a field), the minimization of GWM $$^\mathrm{c}$$ s involves fundamental notions from the theory of finite dimensional algebra. We posit that the properties of GWM $$^\mathrm{c}$$ s unraveled in this paper willprove useful for the study of GWMs defined over richer families of graphs.
BibTeX
@inproceedings{rabusseau2018minimization,
  author = {Guillaume Rabusseau},
  title = {{Minimization of Graph Weighted Models over Circular Strings}},
  booktitle = {FoSSaCS},
  year = {2018},
  url = {https://openreview.net/forum?id=a2P38GjQ1oS},
}

Loading related content...

Figure