ActiveState!

ActivePerl Documentation
Table of Contents

(Usage Statistics)
(about this ver)


* Getting Started
    * Welcome To ActivePerl
    * Release Notes
    * Readme
    * ActivePerl Change Log
* Install Notes
    * Linux
    * Solaris
    * Windows
* ActivePerl Components
    * Overview
    * PPM
    * Windows Specifics
       * OLE Browser
       * PerlScript
       * Perl for ISAPI
       * PerlEZ
* ActivePerl FAQ
    * Introduction
    * Availability & Install
    * Using PPM
    * Docs & Support
    * Windows Specifics
       * Perl for ISAPI
       * Windows 9X/NT/2000
       * Quirks
       * Web Server Config
       * Web programming
       * Programming
       * Modules & Samples
       * Embedding & Extending
       * Using OLE with Perl
* Windows Scripting
    * Active Server Pages
    * Windows Script Host
    * Windows Script Components

Core Perl Documentation


* perl
* perlfaq
* perltoc
* perlbook

* perlsyn
* perldata
* perlop
* perlreftut
* perldsc
* perllol

* perllexwarn
* perldebug

* perlrun
* perlfunc
* perlopentut
* perlvar
* perlsub
* perlmod
* perlpod

* perlstyle
* perlmodlib
* perlmodinstall
* perltrap
* perlport
* perlsec

* perlref
* perlre
* perlform
* perllocale
* perlunicode

* perlboot
* perltoot
* perltootc
* perlobj
* perlbot
* perltie

* perlipc
* perlnumber
* perlfork
* perlthrtut

* perldiag
* perlfaq1
* perlfaq2
* perlfaq3
* perlfaq4
* perlfaq5
* perlfaq6
* perlfaq7
* perlfaq8
* perlfaq9

* perlcompile

* perlembed
* perlxstut
* perlxs
* perlguts
* perlcall
* perlfilter
* perldbmfilter
* perlapi
* perlintern
* perlapio
* perltodo
* perlhack

* perlhist
* perldelta
* perl5005delta
* perl5004delta

* perlamiga
* perlcygwin
* perldos
* perlhpux
* perlmachten
* perlos2
* perlos390
* perlvms
* perlwin32

Pragmas


* attributes
* attrs
* autouse
* base
* blib
* bytes
* charnames
* constant
* diagnostics
* fields
* filetest
* integer
* less
* lib
* locale
* lwpcook
* open
* ops
* overload
* perllocal
* re
* sigtrap
* strict
* subs
* utf8
* vars
* warnings

Libraries


* ActivePerl
    * DocTools
        * TOC
            * RDF
* AnyDBM_File
* Archive
    * Tar
* AutoLoader
* AutoSplit
* B
    * Asmdata
    * Assembler
    * Bblock
    * Bytecode
    * C
    * CC
    * Debug
    * Deparse
    * Disassembler
    * Lint
    * Showlex
    * Stackobj
    * Terse
    * Xref
* Benchmark
* Bundle
    * LWP
* ByteLoader
* Carp
    * Heavy
* CGI
    * Apache
    * Carp
    * Cookie
    * Fast
    * Pretty
    * Push
    * Switch
* Class
    * Struct
* Compress
    * Zlib
* Config
* CPAN
    * FirstTime
    * Nox
* Cwd
* Data
    * Dumper
* DB
* Devel
    * DProf
    * Peek
    * SelfStubber
* Digest
    * HMAC
    * HMAC_MD5
    * HMAC_SHA1
    * MD2
    * MD5
    * SHA1
* DirHandle
* Dumpvalue
* DynaLoader
* English
* Env
* Errno
* Exporter
    * Heavy
* ExtUtils
    * Command
    * Embed
    * Install
    * Installed
    * Liblist
    * MakeMaker
    * Manifest
    * Miniperl
    * Mkbootstrap
    * Mksymlists
    * MM_Cygwin
    * MM_OS2
    * MM_Unix
    * MM_VMS
    * MM_Win32
    * Packlist
    * testlib
* Fatal
* Fcntl
* File
    * Basename
    * CheckTree
    * Compare
    * Copy
    * CounterFile
    * DosGlob
    * Find
    * Glob
    * Listing
    * Path
    * Spec
        * Functions
        * Mac
        * OS2
        * Unix
        * VMS
        * Win32
    * stat
* FileCache
* FileHandle
* FindBin
* Font
    * AFM
* Getopt
    * Long
    * Std
* HTML
    * AsSubs
    * Element
    * Entities
    * Filter
    * Form
    * FormatPS
    * Formatter
    * FormatText
    * HeadParser
    * LinkExtor
    * Parse
    * Parser
    * TokeParser
    * TreeBuilder
* HTTP
    * Cookies
    * Daemon
    * Date
    * Headers
        * Util
    * Message
    * Negotiate
    * Request
        * Common
    * Response
    * Status
* I18N
    * Collate
* IO
    * Dir
    * File
    * Handle
    * Pipe
    * Poll
    * Seekable
    * Select
    * Socket
        * INET
        * UNIX
* IPC
    * Msg
    * Open2
    * Open3
    * Semaphore
    * SysV
* LWP
    * Debug
    * MediaTypes
    * MemberMixin
    * Protocol
    * RobotUA
    * Simple
    * UserAgent
* Math
    * BigFloat
    * BigInt
    * Complex
    * Trig
* MD5
* MIME
    * Base64
    * QuotedPrint
* NDBM_File
* Net
    * Cmd
    * Config
    * Domain
    * DummyInetd
    * FTP
    * hostent
    * libnetFAQ
    * netent
    * Netrc
    * NNTP
    * PH
    * Ping
    * POP3
    * protoent
    * servent
    * SMTP
    * SNPP
    * Time
* O
* ODBM_File
* Opcode
* Pod
    * Checker
    * Find
    * Html
    * InputObjects
    * Man
    * Parser
    * ParseUtils
    * Plainer
    * Select
    * Text
        * Color
        * Termcap
    * Usage
* POSIX
* PPM
    * SOAPClient
    * SOAPServer
* Safe
* SDBM_File
* Search
    * Dict
* SelectSaver
* SelfLoader
* SHA
* Shell
* SOAP
    * Defs
    * Envelope
    * EnvelopeMaker
    * GenericHashSerializer
    * GenericInputStream
    * GenericScalarSerializer
    * Lite
    * OutputStream
    * Packager
    * Parser
    * Transport
        * HTTP
            * Apache
            * CGI
            * Client
            * Server
        * LOCAL
        * MAILTO
        * POP3
        * TCP
    * TypeMapper
* Socket
* Symbol
* Sys
    * Hostname
    * Syslog
* Term
    * ANSIColor
    * Cap
    * Complete
    * ReadLine
* Test
    * Harness
* Text
    * Abbrev
    * ParseWords
    * Soundex
    * Tabs
    * Wrap
* Thread
    * Queue
    * Semaphore
    * Signal
    * Specific
* Tie
    * Array
    * Handle
    * Hash
    * RefHash
    * Scalar
    * SubstrHash
* Time
    * gmtime
    * Local
    * localtime
    * tm
* UDDI
    * Lite
* UNIVERSAL
* URI
    * data
    * Escape
    * file
    * Heuristic
    * ldap
    * URL
    * WithBase
* User
    * grent
    * pwent
* Win32
    * AuthenticateUser
    * ChangeNotify
    * Clipboard
    * Console
    * Event
    * EventLog
    * File
    * FileSecurity
    * Internet
    * IPC
    * Mutex
    * NetAdmin
    * NetResource
    * ODBC
    * OLE
        * Const
        * Enum
        * NEWS
        * NLS
        * TPJ
        * Variant
    * PerfLib
    * Pipe
    * Process
    * Registry
    * Semaphore
    * Service
    * Sound
    * TieRegistry
* Win32API
    * File
    * Net
    * Registry
* WWW
    * RobotRules
        * AnyDBM_File
* XML
    * Element
    * Parser
        * Expat
    * PPD
    * PPMConfig
    * ValidatingElement
* XSLoader

 Algorithm - the theory behind it


NAME

Kleene's Algorithm - the theory behind it

brief introduction


SUPPORTED PLATFORMS

  • Linux
  • Solaris
  • Windows
This module is not included with the standard ActivePerl distribution. It is available as a separate download using PPM.

DESCRIPTION

Semi-Rings

A Semi-Ring (S, +, ., 0, 1) is characterized by the following properties:

  1. )
    a) (S, +, 0) is a Semi-Group with neutral element 0

    b) (S, ., 1) is a Semi-Group with neutral element 1

    c) 0 . a = a . 0 = 0 for all a in S

  2. )
    "+" is commutative and idempotent, i.e., a + a = a

  3. )
    Distributivity holds, i.e.,

    a) a . ( b + c ) = a . b + a . c for all a,b,c in S

    b) ( a + b ) . c = a . c + b . c for all a,b,c in S

  4. )
    SUM_{i=0}^{+infinity} ( a[i] )

    exists, is well-defined and unique

    for all a[i] in S

    and associativity, commutativity and idempotency hold

  5. )
    Distributivity for infinite series also holds, i.e.,
      ( SUM_{i=0}^{+infty} a[i] ) . ( SUM_{j=0}^{+infty} b[j] )
      = SUM_{i=0}^{+infty} ( SUM_{j=0}^{+infty} ( a[i] . b[j] ) )

EXAMPLES:

Operator '*'

(reflexive and transitive closure)

Define an operator called ``*'' as follows:

    a in S   ==>   a*  :=  SUM_{i=0}^{+infty} a^i

where

    a^0  =  1,   a^(i+1)  =  a . a^i

Then, also

    a*  =  1 + a . a*,   0*  =  1*  =  1

hold.

Kleene's Algorithm

In its general form, Kleene's algorithm goes as follows:

    for i := 1 to n do
        for j := 1 to n do
        begin
            C^0[i,j] := m(v[i],v[j]);
            if (i = j) then C^0[i,j] := C^0[i,j] + 1
        end
    for k := 1 to n do
        for i := 1 to n do
            for j := 1 to n do
                C^k[i,j] := C^k-1[i,j] + 
                            C^k-1[i,k] . ( C^k-1[k,k] )* . C^k-1[k,j]
    for i := 1 to n do
        for j := 1 to n do
            c(v[i],v[j]) := C^n[i,j]

Kleene's Algorithm and Semi-Rings

Kleene's algorithm can be applied to any Semi-Ring having the properties listed previously (above). (!)

EXAMPLES:

  • S1 = ({0,1}, |, &, 0, 1)

    G(V,E) be a graph with set of vortices V and set of edges E:

    m(v[i],v[j]) := ( (v[i],v[j]) in E ) ? 1 : 0

    Kleene's algorithm then calculates

    c^{n}_{i,j} = ( path from v[i] to v[j] exists ) ? 1 : 0

    using

    C^k[i,j] = C^k-1[i,j] | C^k-1[i,k] & C^k-1[k,j]

    (remember 0* = 1* = 1 )

  • S2 = (pos. reals with 0 and +infty, min, +, +infty, 0)

    G(V,E) be a graph with set of vortices V and set of edges E, with costs m(v[i],v[j]) associated with each edge (v[i],v[j]) in E:

    m(v[i],v[j]) := costs of (v[i],v[j])

    for all (v[i],v[j]) in E

    Set m(v[i],v[j]) := +infinity if an edge (v[i],v[j]) is not in E.

    ==> a* = 0 for all a in S2

    ==> C^k[i,j] = min( C^k-1[i,j] ,

    C^k-1[i,k] + C^k-1[k,j] )

    Kleene's algorithm then calculates the costs of the ``shortest'' path from any v[i] to any other v[j]:

    C^n[i,j] = costs of "shortest" path from v[i] to v[j]

  • S3 = (Pot(Sigma*), union, concat, {}, {''})

    M in DFA(Sigma) be a Deterministic Finite Automaton with a set of states Q, a subset F of Q of accepting states and a transition function delta : Q x Sigma --> Q.

    Define

    m(v[i],v[j]) :=

    { a in Sigma | delta( q[i] , a ) = q[j] }

    and

    C^0[i,j] := m(v[i],v[j]);

    if (i = j) then C^0[i,j] := C^0[i,j] union {''}

    ({''} is the set containing the empty string, whereas {} is the empty set!)

    Then Kleene's algorithm calculates the language accepted by Deterministic Finite Automaton M using

    C^k[i,j] = C^k-1[i,j] union

    C^k-1[i,k] concat ( C^k-1[k,k] )* concat C^k-1[k,j]

    and

    L(M) = UNION_{ q[j] in F } C^n[1,j]

    (state q[1] is assumed to be the ``start'' state)

    finally being the language recognized by Deterministic Finite Automaton M.

Note that instead of using Kleene's algorithm, you can also use the ``*'' operator on the associated matrix:

Define A[i,j] := m(v[i],v[j])

==> A*[i,j] = c(v[i],v[j])

Proof:

A* = SUM_{i=0}^{+infty} A^i

where A^0 = E_{n}

(matrix with one's in its main diagonal and zero's elsewhere)

and A^(i+1) = A . A^i

Induction over k yields:

A^k[i,j] = c_{k}(v[i],v[j])

k = 0:
c_{0}(v[i],v[j]) = d_{i,j}

with d_{i,j} := (i = j) ? 1 : 0

and A^0 = E_{n} = [d_{i,j}]

k-1 -> k:
c_{k}(v[i],v[j])

= SUM_{l=1}^{n} m(v[i],v[l]) . c_{k-1}(v[l],v[j])

= SUM_{l=1}^{n} ( a[i,l] . a[l,j] )

= [a^{k}_{i,j}] = A^1 . A^(k-1) = A^k

qed

In other words, the complexity of calculating the closure and doing matrix multiplications is of the same order O( n^3 ) in Semi-Rings!


SEE ALSO

Math::MatrixBool(3), Math::MatrixReal(3), DFA::Kleene(3).

(All contained in the distribution of the ``Set::IntegerFast'' module)

Dijkstra's algorithm for shortest paths.


AUTHOR

This document is based on lecture notes and has been put into POD format by Steffen Beyer <sb@sdm.de>.


COPYRIGHT

Copyright (c) 1997 by Steffen Beyer. All rights reserved.

 Algorithm - the theory behind it