Word problem for boolean expressions
in [Theory]
|
Prev: Diffused concern for too many papers on PvsNP
Next: Second CALL FOR PAPERS: WfPM'08, September 2008, Timisoara, ROMANIA
From: Mitch on 2 Jul 2008 11:35 On Jul 2, 9:11 am, sanchopanch...(a)web.de wrote: > Hello, > > if you consider the alphabet S={\wedge,\vee.\not,(,),x,0,1} one can > think of all boolean expressions B as a language over this alphabet. > Is the problem of deciding weather a string s of S* is in B or not in > P? My guess is that the easiest way to see this is to construct a at > least context-free grammar which produces B. Hence the problem is > decidable because the word problem for context free grammars is in P > by the CYK algorithm. I only want to know if that is possible. Sure it's possible. The language of boolean expressions has a simple context free grammar. Deciding membership of a string in a CFG is in P. > Moreover let 3CNF be the language of all boolean expressions in 3- > conjunctive normal form over S, i.e. every expression is of the form > (y1\vee y2\vee y3)\wedge (z1\vee z2\vee z3) \wedge ... where yi,zi are > of the form x_i or \not x_i. Is the word problem of 3CNF decidable in > polynomial time, too? 3CNF is even easier...there is a regular expression for 3CNF. Deciding membership of a regexp (the good ol'fashioned kind, not the Perl/Java/ Emacs extended kind) is in P... hm... maybe even in L (deterministic logspace). Don't get mixed up between the syntax of the languages involved here (deciding if a string is of proper form) and the more logical/semantic properties (deciding satisfiability). They are separate problems. Mitch
From: sanchopancho80 on 2 Jul 2008 12:12
On 2 Jul., 17:35, Mitch <maha...(a)gmail.com> wrote: > On Jul 2, 9:11 am, sanchopanch...(a)web.de wrote: > > > Hello, > > > if you consider the alphabet S={\wedge,\vee.\not,(,),x,0,1} one can > > think of all boolean expressions B as a language over this alphabet. > > Is the problem of deciding weather a string s of S* is in B or not in > > P? My guess is that the easiest way to see this is to construct a at > > least context-free grammar which produces B. Hence the problem is > > decidable because the word problem for context free grammars is in P > > by the CYK algorithm. I only want to know if that is possible. > > Sure it's possible. The language of boolean expressions has a simple > context free grammar. Deciding membership of a string in a CFG is in > P. > > > Moreover let 3CNF be the language of all boolean expressions in 3- > > conjunctive normal form over S, i.e. every expression is of the form > > (y1\vee y2\vee y3)\wedge (z1\vee z2\vee z3) \wedge ... where yi,zi are > > of the form x_i or \not x_i. Is the word problem of 3CNF decidable in > > polynomial time, too? > > 3CNF is even easier...there is a regular expression for 3CNF. Deciding > membership of a regexp (the good ol'fashioned kind, not the Perl/Java/ > Emacs extended kind) is in P... hm... maybe even in L (deterministic > logspace). Thanks. > Don't get mixed up between the syntax of the languages involved here > (deciding if a string is of proper form) and the more logical/semantic > properties (deciding satisfiability). They are separate problems. Thanks, I know. |