Abstract : In this paper we present a version of mobile ambients, called parMA, having a weak form of replication and a parallel semantics. We investigate how parMA can solve intractable problems in a polynomial number of computational steps. We use parMA to give a semiuniform solution to a well-known strong NP-complete problem, namely to the Boolean satisfiability problem (SAT).
https://hal.inria.fr/hal-01529591
Contributor : Hal Ifip
<>
Submitted on : Wednesday, May 31, 2017 - 9:59:54 AM
Last modification on : Wednesday, May 31, 2017 - 10:00:58 AM
Long-term archiving on: Wednesday, September 6, 2017 - 2:33:15 PM
Bogdan Aman, Gabriel Ciobanu. Coordinating Parallel Mobile Ambients to Solve SAT Problem in Polynomial Number of Steps. 14th International Conference on Coordination Models and Languages (COORDINATION), Jun 2012, Stockholm, Sweden. pp.122-136, ⟨10.1007/978-3-642-30829-1_9⟩. ⟨hal-01529591⟩
