Cheap and Secure Web Hosting Provider : See Now

What problems are solvable in Datalog?

, , No Comments
Problem Detail: 

Datalog is not Turing complete. It does however have the wonderful property of not being order sensitive. What problems can be solved in Datalog? Where does it fit in the Chomsky hierarchy, i.e. what abstract machine does it model?

Asked By : Filip Haglund
Answered By : Yuval Filmus

According to these slides, deciding whether a single atom is generated by a Datalog program is EXPTIME-complete. There are several corresponding machine models, for example an EXPTIME Turing machine or an EXPTIME RAM machine.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/64396

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback