Coordinating Parallel Mobile Ambients to Solve SAT Problem in Polynomial Number of Steps

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).
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

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

File

978-3-642-30829-1_9_Chapter.pd...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

46

Files downloads

87