python modal logic K solver -

i working on modal logic tableau solver implemented in python (2.7.5 version). have function translates input string tableau format is:

input：

~p ^ q 

parsed:

['and',('not', 'p'), 'q'] 

parsed , alpha rule applied:

[('not', 'p'), 'q'] 

now, dealt alpha formulas intersection, double negations etc. problem encountering beta formulas , example union.

for union formula need write function splits 1 list in 2 lists, example:

input:

('and', 's', ('or', (not,'r'), 'q')) 

outputs:

1st list ('s',('not','r')) 2nd list ('s','q') 

i can once, how can recursively scan formula , generate these list later can scan them , verify whether closed or not?

the final goal of create tableau solver generates graph model or return answer formula unsatisfiable.

it' interesting project :). i'm myself in thesis modal logic right now.

i'm first of all, advising use intohylo input format, quite standard in existing solvers.

the intohylo format looking follow:

  file ::= ['begin'] dml ['end']    fml ::= '(' fml ')'                        (* parentheses *)         | '1' | 'true' | 'true' | 'true'     (* truth *)         | '0' | 'false' | 'false' | 'false'  (* falsehood *)         | '~' fml | '-' fml                  (* negation *)         | '<>' fml | '<' id '>' fml          (* diamonds *)         | '[]' fml | '[' id ']' fml          (* boxes *)         | fml '&' fml                        (* conjunction *)         | fml '|' fml                        (* disjunction *)         | fml '->' fml                       (* implication *)         | fml '<->' fml                      (* equivalence *)         | id                                 (* prop. var. *)     identifiers (id) arbitrary nonempty alphanumeric sequences: (['a'-'z' 'a'-'z' '0'-'9']+) 

to simplify parsing of formula , focus on real problem : solving instance. advise use existing parser flex/bison.

by looking on internet problem, (i'm far being expert in python) looks library "http://pyparsing.wikispaces.com" reference parsing.

and after, using bison follow, file parsed.

here bison file (for using flex/bison in solver c++):

/*  *  *  compile bison.  */  /*** code inserted @ begin of file. ***/ %{      #include <stdlib.h>   #include <list>   #include "formula.h"    // yylex exists   extern int yylex();   extern char yytext[];    void yyerror(char *msg); %}   /*** bison declarations ***/ %union {    bool         bval;    operator_t  opval;    char        *sval;    termptr     *term;       }  %token lround rround   %left iff %left imp %left or %left , %right diamond  %right box  %right not   %token value %token identifier  %type<bval> value %type<sval> identifier   %type<term> formula booleanvalue booleanformula modalformula propositionalvariable unaryformula %type<opval> binarybooloperator unarybooloperator modaloperator  %start start  %%  start:   | formula  { (formula::getformula()).setroot(*$1); } ;  formula:   booleanformula               { $$ = $1; }          | modalformula                 { $$ = $1; }          | unaryformula                 { $$ = $1; }          | lround formula rround        { $$ = $2; } ;  booleanvalue:   value { $$ = new termptr( (term*) new booleanvalue($1) ); } ;  propositionalvariable:   identifier { $$ = new termptr( (term*) new propositionalvar($1) ); } ;  booleanformula:   formula binarybooloperator formula {                         $$ = new termptr( (term*) new booleanop(*$1, *$3, $2) );  /* can (a or b) or (a , b) */                       delete($3);                        delete($1);                    }  |                 formula imp formula {                        ($1)->negate();                       $$ = new termptr( (term*) new booleanop(*$1, *$3, o_or) ); /* -> b can written : (¬a v b) */                       delete($3);                        delete($1);                   }  |                 propositionalvariable iff propositionalvariable {                        propositionalvar *copy1 = new propositionalvar( *((propositionalvar*)$1->getptr()) );                       propositionalvar *copy3 = new propositionalvar( *((propositionalvar*)$3->getptr()) );                        termptr negated1( (term*)copy1, $1->isnegated() );                        termptr negated3( (term*)copy3, $3->isnegated() );                        negated1.negate();                        negated3.negate();                        termptr or1( (term*) new booleanop(negated1, *$3, o_or) ); /* or1 = (¬a v b) */                       termptr or2( (term*) new booleanop(negated3, *$1, o_or) ); /* or2 = (¬b v a) */                        $$ = new termptr( (term*) new booleanop(or1, or2, o_and) ); /* add : (or1 , orb) */                        delete($3);                        delete($1);                   }                            ;  modalformula:   modaloperator lround formula rround  {                    $$ = new termptr( (term*) new modalop(*$3, $1) );                   delete($3);                 } |                 modaloperator modalformula  {                    $$ = new termptr( (term*) new modalop(*$2, $1) );                   delete($2);                 }         |                 modaloperator unaryformula  {                    $$ = new termptr( (term*) new modalop(*$2, $1) );                   delete($2);                 }    ;  unaryformula:   booleanvalue                 { $$ = $1; }  |               propositionalvariable        { $$ = $1; }  |                 unarybooloperator unaryformula {                    if ($1 == o_not) {                     ($2)->negate();                    }                                     $$ = $2;                  } |                 unarybooloperator modalformula {                    if ($1 == o_not) {                     ($2)->negate();                    }                                     $$ = $2;                  }                 |                 unarybooloperator lround formula rround {                    if ($1 == o_not) {                     ($3)->negate();                    }                                     $$ = $3;                  } ;   modaloperator:   box          { $$ = o_box; } |                diamond      { $$ = o_diamond; } ;  binarybooloperator:   ,     { $$ = o_and; } |                     or      { $$ = o_or; } ;  unarybooloperator:   not      { $$ = o_not; } ;   /*** code inserted @ , of file ***/ %%  void yyerror(char *msg) {   printf("parser: %s", msg);   if (yytext[0] != 0)     printf(" near token '%s'\n", yytext);   else      printf("\n");   exit(-1);    } 

by adapting it, able parse , recursively modal logic formula :).

and if later, want challenge solver existing tableau solver (like spartacus example). dont forget theses solvers time, answering maximal open tableau, sure faster if want find kripke model of solution ;)

i hope manage question, less theoretical, unfortunately don't master python :/.

wish best solver;

best regards.

---

if accept proposition of using intohylo, worked on checker of kripke models modal logic k. can find here: http://www.cril.univ-artois.fr/~montmirail/mdk-verifier/

it has been published in paar'2016:

on checking kripke models modal logic k, jean-marie lagniez, daniel le berre, tiago de lima, , valentin montmirail, proceedings of fifth workshop on pratical aspect of automated reasoning (paar 2016)