Grants » Membrane Computing and Biologically Inspired Calculi: Computability, Complexity, Causality
Cod proiect: IDEI 919/2011
Proiect finanțat de Unitatea Executiva pentru Finantarea Invatamantului Superior, a Cercetarii, Dezvoltarii si Inovarii (UEFISCDI).
Perioada de implementare: 2011 – 2016
Descriere: :
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.
View details
Proiect finanțat de Unitatea Executiva pentru Finantarea Invatamantului Superior, a Cercetarii, Dezvoltarii si Inovarii (UEFISCDI).
Perioada de implementare: 2011 – 2016
Descriere: :
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.
View details