Overview

Arden's rule


Related Overviews

 

'Arden's rule' can also refer to...

 

More Like This

Show all results sharing this subject:

  • Computing

GO

Show Summary Details

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 = AXB

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).

Subjects: Computing.


Reference entries

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