Computer science often treats formal languages and linear algebra as separate worlds. Formal languages deal with discrete, symbolic structures—strings, regular expressions, and grammars—while linear algebra operates in continuous vector spaces.
However, a powerful research direction bridges this gap by mapping strings and automata directly into matrix spaces. By translating symbolic operations into matrix algebra, researchers can bypass combinatorial bottlenecks, perform real-time probabilistic inference, and apply continuous optimization techniques to discrete language learning.
Concatenation as Matrix Multiplication
To understand why this mapping works, consider the core operation of formal languages: string concatenation. When we append the symbol $b$ to the symbol $a$ to form the string $ab$, the operation is associative but non-commutative ($ab \neq ba$).
Matrix multiplication shares exactly these algebraic properties. If we map every discrete symbol in an alphabet to a small, square matrix, we can simulate string concatenation purely through matrix multiplication.
Symbolic Space: a + b = ab
| | |
v v v
Algebraic Space: Matrix(a) x Matrix(b) = Matrix(ab)
In Counting Vanishing Matrix-Vector Products, Cornelius Brand et al. leverage this exact mechanism. By representing discrete symbols as small-dimension matrices, they show that complex string-matching puzzles can be reduced to determining whether a sequence of matrix transformations results in a zero vector.
This algebraic reduction provides a geometric toolkit for analyzing system behavior. For instance, in Polynomial automata: Zeroness and applications, Aditya Sharad et al. map string concatenation to $2 \times 2$ matrix multiplications. This allows them to translate streaming string transducers into polynomial dynamical systems, making it possible to compute explicit complexity bounds for program equivalence.
The same principle applies to querying dynamic data. In Dynamic direct access of MSO query evaluation over strings, the authors demonstrate that evaluating queries over a changing string can be reduced to an algebraic word problem. By assigning a transition matrix to each character, the product of these matrices over a specific substring yields the exact number of ways an automaton can transition between states, allowing for rapid query updates when characters change.
Compiling Regular Expressions: From Loops to Matrix Inversion
If string concatenation maps to matrix multiplication, how do we handle more complex regular language operations like union ($A \cup B$) or the Kleene star ($A^*$)?
Linear algebra provides elegant equivalents for both:
- Union maps directly to matrix addition ($A + B$).
- Kleene Star represents repeating an operation zero or more times ($I + A + A^2 + A^3 + \dots$). Algebraically, this infinite sum is a geometric series of matrices. If the system is stable, this series converges exactly to a matrix inverse: $(I - A)^{-1}$.
This mapping allows us to compile entire regular expressions into linear algebra operations. In Incremental Computation of Infix Probabilities for Probabilistic Finite Automata, Marco Cognetta et al. use this framework to calculate infix probabilities—the likelihood that a specific phrase appears anywhere inside a larger sequence.
By converting regular expressions into matrix addition, multiplication, and inversion, they compute these probabilities analytically. In Online Infix Probability Computation for Probabilistic Finite Automata, the authors extend this to an online algorithm. Because the underlying operations are just matrix transformations, the model can update probabilities on-the-fly as a stream of text arrives. Crucially, using unambiguous regular expressions ensures that the matrix algebra naturally avoids double-counting overlapping strings, eliminating the need for expensive automaton intersection algorithms.
Commutativity and the Geometry of Symbol Counts
What happens if the order of symbols does not matter? In commutative grammars and multiset languages, we only care about how many times each symbol appears, not their sequence.
When non-commutativity is stripped away, matrix spaces simplify into vector spaces. We can represent a string as a Parikh image—a vector where each coordinate corresponds to the count of a specific symbol. Adding a character to a multiset is simply adding a basis vector.
Eryk Kopczyński demonstrates in Complexity of Problems of Commutative Grammars that this vector space representation allows linear algebraic tools to efficiently characterize the reachability and generative properties of commutative formal grammars. To operationalize this algorithmically, David Chiang et al. show in Algorithms and Training for Weighted Multiset Automata and Regular Expressions how auxiliary Boolean matrices can track symbol occurrences. This algebraic formulation allows the model to handle shuffle products and overlapping alphabets much more efficiently than traditional, state-explosive string automata.
Learning and Optimization via Matrix Factorization
Embedding languages into continuous matrix spaces does more than speed up execution—it unlocks continuous optimization techniques for learning grammars from raw data.
In Compositional Matrix-Space Models of Language, Sebastian Rudolph et al. introduce a framework where a sequence of tokens is deemed grammatically valid if the product of their representative matrices satisfies specific linear inequalities. This unifies statistical word embeddings with symbolic grammar rules into a single, differentiable mathematical framework.
When learning hierarchical structures like Weighted Context-Free Grammars (WCFGs), traditional discrete algorithms like Expectation-Maximization frequently get stuck in local optima. In Unsupervised Spectral Learning of WCFG as Low-rank Matrix Completion, Raphaël Bailly et al. solve this by reformulating the grammar using vectors and bilinear operators. They arrange observed string frequencies into a large matrix called a Hankel matrix. Because the grammar's recursive rules manifest as linear constraints on this matrix, finding the simplest grammar that explains the data reduces to a convex low-rank matrix completion problem, guaranteeing an optimal global solution.
Discrete Grammar Rules ---> Linear Constraints on Hankel Matrix ---> Low-Rank Matrix Completion
(Prone to local optima) (Convex, globally optimal)
Finally, matrix factorization provides a tool for minimizing the state-space of probabilistic systems. In On Restricted Nonnegative Matrix Factorization, Dmitry Chistikov et al. prove that finding the minimal covering for a Labelled Markov Chain is exactly equivalent to computing a restricted nonnegative matrix factorization (RNMF) of its backward transition matrix. This geometric connection reveals that the fundamental limits of compressing a probabilistic automaton are dictated by the algebraic rank of its transition matrix.
This same structural translation applies to broader dynamic systems; as Chalee Asavathiratham demonstrates in Linear Algebra Approach to Separable Bayesian Networks, using event and marginalization matrices allows researchers to translate complex probabilistic network dependencies into clean, trackable linear transformations.
Key Foundational Work
Linear Algebra Approach to Separable Bayesian Networks (2006) — contributed 1 concept elements to this direction.
Compositional Matrix-Space Models of Language (2010) — contributed 1 concept elements to this direction.