Overview

Kleene's theorem


Show Summary Details

Quick Reference

1 on regular expressions. A theorem in formal language theory proposed by Stephen Kleene and stating that a language is definable by a regular expression if and only if it is recognized by a finite-state automaton. A regular expression equivalent to a finite-state automaton can be found by solving a set of simultaneous linear equations (see linear grammar, Arden's rule). Regular expressions were first used to characterize the power of certain neural networks.

2 on fixed points. See fixed-point theorem.

Subjects: Computing.


Reference entries

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