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).
Type de document :
Communication dans un congrès
Marjan Sirjani. 14th International Conference on Coordination Models and Languages (COORDINATION), Jun 2012, Stockholm, Sweden. Springer, Lecture Notes in Computer Science, LNCS-7274, pp.122-136, 2012, Coordination Models and Languages. 〈10.1007/978-3-642-30829-1_9〉
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01529591
Contributeur : Hal Ifip <>
Soumis le : mercredi 31 mai 2017 - 09:59:54
Dernière modification le : mercredi 31 mai 2017 - 10:00:58
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 14:33:15

Fichier

978-3-642-30829-1_9_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Bogdan Aman, Gabriel Ciobanu. Coordinating Parallel Mobile Ambients to Solve SAT Problem in Polynomial Number of Steps. Marjan Sirjani. 14th International Conference on Coordination Models and Languages (COORDINATION), Jun 2012, Stockholm, Sweden. Springer, Lecture Notes in Computer Science, LNCS-7274, pp.122-136, 2012, Coordination Models and Languages. 〈10.1007/978-3-642-30829-1_9〉. 〈hal-01529591〉

Partager

Métriques

Consultations de la notice

20

Téléchargements de fichiers

13