Time-freeness and clock-freeness and related concepts in P systems
Închide
Conţinutul numărului revistei
Articolul precedent
Articolul urmator
526 0
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: Theoretical Computer Science, 2020, nr. 805, pp. 127-143. ISSN 0304-3975. DOI: https://doi.org/10.1016/j.tcs.2018.09.009
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Theoretical Computer Science
Numărul 805 / 2020 / ISSN 0304-3975 /ISSNe 1879-2294

Time-freeness and clock-freeness and related concepts in P systems

DOI:https://doi.org/10.1016/j.tcs.2018.09.009

Pag. 127-143

Alhazov Artiom12, Freund Rudolf3, Ivanov Sergiu45, Pan Linqiang2, Song Bosheng2
 
1 Vladimir Andrunachievici Institute of Mathematics and Computer Science,
2 Huazhong University of Science and Technology,
3 Technical University of Vienna,
4 IBISC, Universite Evry,
5 Universitatea Paris-Saclay
 
 
Disponibil în IBN: 15 octombrie 2020


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, different 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, different applications of the same rule may last for a different 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 efficiently 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 fixed family of modes, and compare mode-freeness with clock-freeness.

Cuvinte-cheie
Clock-freeness, Mode-freeness, P system, Time-freeness