Time-freeness and Clock-freeness and Related Concepts in P Systems
Închide
Articolul precedent
Articolul urmator
335 1
Ultima descărcare din IBN:
2022-06-13 20:29
SM ISO690:2012
ALHAZOV, Artiom, FREUND, Rudolf, IVANOV, Sergiu, PAN, Linqiang, SONG, Bosheng. Time-freeness and Clock-freeness and Related Concepts in P Systems. In: Brainstorming Week On Membrane Computing, 31 ianuarie - 3 februarie 2017, Sevilla. Sevilla, Spania: Sevilla University, 2017, Ediția a 15-a, pp. 43-70. ISBN 978-84-946316-1-0.
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Brainstorming Week On Membrane Computing
Ediția a 15-a, 2017
Masa rotundă "15th Brainstorming Week on Membrane Computing"
Sevilla, Spania, 31 ianuarie - 3 februarie 2017

Time-freeness and Clock-freeness and Related Concepts in P Systems


Pag. 43-70

Alhazov Artiom12, Freund Rudolf3, Ivanov Sergiu45, Pan Linqiang26, Song Bosheng2
 
1 Institute of Mathematics and Computer Science ASM,
2 Huazhong University of Science and Technology,
3 Faculty of Informatics, TU Wien,
4 Université Paris-Est-Créteil,
5 Necunoscută, Franţa,
6 Necunoscută, China
 
 
Disponibil în IBN: 14 mai 2021


Rezumat

In the majority of models of P systems, rules are applied at the ticks of a global clock and their products are introduced into the system for the following step. In timed P systems, di erent integer durations are statically assigned to rules; time-free P systems are P systems yielding the same languages independently of these durations. In clock-free P systems, durations are real and are assigned to individual rule applications; thus, di erent applications of the same rule may last for a di erent amount of time. In this paper, we formalise timed, time-free, and clock-free P system within a framework for generalised parallel rewriting. We then explore the relationship between these variants of semantics. We show that clock-free P systems cannot eciently solve intractable problems. Moreover, we consider un-timed systems where we collect the results using arbitrary timing functions as well as un-clocked P systems where we take the union over all possible per-instance rule durations. Finally, we also introduce and study mode-free P systems, whose results do not depend on the choice of a mode within a xed family of modes, and compare mode-freeness with clock-freeness.