🚀 go-pugleaf

In article <4500@daimi.dk> kimskak@daimi.dk (Kim Skak Larsen) writes:
>
>How difficult is resolution of propositional Horn clauses,
>i.e. consider a prolog program without variables that looks
>something like
>                    a :- b,c.
>                    b :- c.
>                    c.
>
...
>What is the complexity of answering queries such as 
>
>                    a?

Your example:

		a :- b, c.  b :- c.  c.  :- a.

is actually a disguised version of this:

* Given the grammar:
*    Start symbol: *start
*    Nonterminals: a, b, c
*    Terminals: *c
*    Productions:
* 	  *start -> a
* 	  a -> b c
* 	  b -> c
* 	  c -> *c
* 
* Prove that the corresponding language is non-empty.

I think the corresponding general problem is NP-complete.