## Quick Reference

A formal language can be specified by means of equations, based on operations on languages. Arden's rule states that *A***B* is the smallest language that is a solution for *X* in the linear equation

*X* = *AX* ∪ *B*

where *X, A, B* are sets of strings. (For notation, **see** union, concatenation, Kleene star.) *A***B* is furthermore the only solution, unless *A* contains the empty string, in which case *A***B*′ is a solution for any subset *B*′ of *B*.

Although simple, Arden's rule is significant as one of the earliest fixed-point results on equation solving in computer science. In conjunction with the normal process of eliminating variables, it can be used to solve any set of simultaneous linear equations over sets of strings. See also Kleene's theorem (on regular expressions).

**From:**
Arden's rule
in
A Dictionary of Computing »

*Subjects:*
Computing.

## Related content in Oxford Index

##### Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.