Coordinating Parallel Mobile Ambients to Solve SAT Problem in Polynomial Number of Steps - Archive ouverte HAL Access content directly
Conference Papers Year : 2012

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

(1) , (1)
1

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).
Fichier principal
Vignette du fichier
978-3-642-30829-1_9_Chapter.pdf (309.56 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01529591 , version 1 (31-05-2017)

Licence

Attribution - CC BY 4.0

Identifiers

Cite

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⟩
30 View
44 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More