Delta-language implementation

by Yury Serdyuk

    The Delta-language implementation is a package of the functions encoded on programming language LISP. This package may be used for evaluation of the arbitrary language terms on any given graphs.

    The programs from the package may be executed with any interpreter/compiler that support the Common Lisp standard.

    The main program from the package is calling as follows:

    (compute '<name of a file with graph>

                   '<name of a file with term> )


The syntax of the terms and formulas:

                                                TERMS

a) <integer>                                                                       ( constant )

b) <identifier>                                                                    ( variable )

c) (ENUM (atr1 t1) (atr2 t2)  ... (atrn tn) )                          ( enumeration )

d) (TC t)                                                                            ( transitive closure )

e) (U t)                                                                               ( union )

f) (D e v)                                                                            ( decoration )

g) (FIX <q-var> <atr-var> <var> <set-term> <formula>)  ( nonmonotone fixpoint )

h) (<image-term> <atr-var> <var> <set-term> <formula>) ( separation-image )

                                              FORMULAE

a) T,NIL                                                        ( constants )

b) (~ f)                                                           ( negation )

c) (f1 & f2)                                                     ( conjunction )

d) (f1 ! f2)                                                       ( disjunction )

e) ( (atr t1) @ t2)                                            ( membership )

f) ( t1 = t2 )                                                     ( equality )                    

g) (A <atr-var> <var> <term> <formula> )      ( bounded universal quantifier )

h) (E <atr-var> <var> <term> <formula> )       ( bounded existential quantifier )


                                         GRAPH REPRESENTATION BY LISTS:

(  k   (  ( n1  (  (atr11 m1)  (atr12 m2)  ...   (atr1s ms)  )  )

            ( n2  (                    .    .   .                                 )   )

                                        .    .   .

            ( ni   NIL                                                           )       (empty set)

                                        .    .   .

            ( nj    <atom>                                                     )       (urelement)

                                        .    .   .

            ( nk  (                    .    .   .                                 )   )

        )

)

        Here k is the number of vertices in graph,

        ( nl  ( (atrl1 m1)       . . .   (atrls ms)  )  )   - vertex description :

                                                                       nl - vertex number,

                                                                       atrl1, ... ,atrls - attributes of the direct

                                                                               successors ("elements") of vertex ("set") nl,

                                                                        m1, ... ,ms - the numbers of the direct

                                                                               successors ("elements") of vertex ("set") nl


There are samples of the work with program.

The package may be downloaded from here. (Sorry, the comments in program are only in Russian).


This work is supported by RBRF (project 96-01-01717) and by INTAS (project 93-0972)