Membrane Computing and Biologically Inspired Calculi: Computability, Complexity, Causality

The main concepts of the project are computability, complexity and causality in the context of membrane systems, process calculi, Petri nets and other related formalisms. Computability and complexity are cornerstones of theoretical computer science, while causality is an issue without a generally accepted formal characterization. We intend to study the computability power of concurrent systems in order to find a minimal set of ingredients (number of compartments and involved resources) for which the formalisms are Turing complete. Focusing on computational efficiency, we want to show that concurrent systems (in particular biologically inspired calculi) can solve hard problems (e.g. SAT and QBF) in polynomial time. We intend to obtain the causal links between the components of the system without the introduction of external ingredients.

Participare ARFI

Instituție coordonatoare

Denumirea completă

Membrane Computing and Biologically Inspired Calculi: Computability, Complexity, Causality

Codul proiectului

IDEI 919/2011

Managementul proiectului

Gabriel Ciobanu

Parteneri

-

Perioada de desfășurare

2011-2016

Tipul proiectului

Linia de finanțare

IDEI - Proiecte de cercetare exploratorie

Finanțator

Unitatea Executiva pentru Finantarea Invatamantului Superior, a Cercetarii, Dezvoltarii si Inovarii

Buget

1274900 RON

Buget ARFI

1274900 RON

Pagina oficială