What is Kleene?

Kleene is a free, open-source programming language for building and manipulating finite-state machines (FSMs). Programmers can specify FSMs—including acceptors and two-projection transducers—using regular expressions, right-linear phrase-structure grammars, and rule-like notations. The FSMs can be unweighted, or weighted under the Tropical Semiring.

Kleene can be used to build natural-language applications including tokenizers, morphological analyzers, part-of-speech taggers and shallow parsers.

Pre-edited Kleene scripts can be executed from the command line, and there is a graphical user interface (GUI) for interactive learning and experimentation.

As far as possible and appropriate, Kleene uses a Perl-like regular-expression syntax that is already familiar to many programmers. The implementation is heavily dependent on the OpenFst library from Google Labs and NYU's Courant Institute, but it borrows some powerful semantic features, including the treatment of “other” (also known as “unknown”) symbols, from the Xerox Finite State Toolkit. Kleene supports language-restriction expressions and alternation rules, based on algorithms by Måns Huldén.

Kleene is named in honor of American mathematician Stephen Cole Kleene, who investigated the properties of regular sets, including regular languages, and invented the metalanguage of regular expressions, which is the foundation of Kleene-language syntax.

What's New in Version

What was New in Version

  • Fixed a GUI bug that caused some output lines to be skipped.

What was New in Version

  • Support for reduplication, modeled on Foma's _eq() function
  • “Transducer-style” alternation rules, also inspired by Foma
  • New assert <boolean> and require <boolean> statements
  • A downloadable script demonstrating weighted spelling correction, modeled on an example by Måns Huldén
  • A downloadable script implementing morphological analysis for Spanish verbs (incomplete, work in progress)

Platforms: OS X and Linux

Kleene currently runs on Mac OS X and Linux. Pre-compiled binaries are available from the download page. Windows users can run Kleene by installing a virtual-machine framework such as VirtualBox, creating a Linux VM (e.g., a Linux Mint or Ubuntu virtual machine) within VirtualBox, and then installing Kleene in the Linux virtual machine.

Apache License, Version 2

Kleene is open-source and was released by SAP AG under the Apache License, Version 2, which is a permissive license allowing even commercial usage. See the full license description at the Apache License Website.

Kleene User Manual

The Kleene User Manual, over 300 pages, is work in progress and is available from the download page.

Beta Status

Kleene is effectively a private hobby development project, still in beta status, and it has not been extensively tested. There are at this time no significant applications written with Kleene, and the syntax might still be changed in any way. Some of my friends have alarmed me by asking when they could start using Kleene for serious projects, and I can only urge caution and experimentation at this time.

Release History

2015-09-29: Candidate beta release

2014-07-08: Beta release

2014-05-22: Candidate beta release

2013-12-??: The server died

2013-06-15: Stealth beta release