Companions and an Essential Motion of a Reaction System

• Autorzy: Genova Daniela , Hoogeboom Hendrik Jan , Jonoska Nataša

Identyfikatory

DOI

10.3233/FI-2020-1953

• Języki publikacji: EN

Abstrakty

EN

For a family of sets we consider elements that belong to the same sets within the family as companions. The global dynamics of a reactions system (as introduced by Ehrenfeucht and Rozenberg) can be represented by a directed graph, called a transition graph, which is uniquely determined by a one-out subgraph, called the 0-context graph. We consider the companion classes of the outsets of a transition graph and introduce a directed multigraph, called an essential motion, whose vertices are such companion classes. We show that all one-out graphs obtained from an essential motion represent 0-context graphs of reactions systems with isomorphic transition graphs. All such 0-context graphs are obtained from one another by swapping the outgoing edges of companion vertices.

Słowa kluczowe

EN

directed graphs; dynamics of reaction systems; equivalence of reaction systems; graph isomorphism; graphs on posets

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 175, nr 1-4
• Strony: 187--199
• Opis fizyczny: Bibliogr. 6 poz., rys.

Twórcy

autor

Genova Daniela

• Department of Mathematics and Statistics, University of North Florida, Jacksonville, FL 32224, USA

autor

Hoogeboom Hendrik Jan

• LIACS, Leiden University, The Netherlands

autor

Jonoska Nataša

• Department of Mathematics and Statistics, University of South Florida, Tampa, USA

Bibliografia

• [1] R. Brijder, A. Ehrenfeucht, M. Main, G. Rozenberg: A Tour of Reaction Systems. International Journal of Foundations of Computer Science 22 (2011) 1499-1517. doi:10.1142/S0129054111008842.
• [2] A. Dennunzio, E. Formenti, L. Manzoni, A.E. Porreca: Reachability in Resource-Bounded Reaction Systems. Language and Automata Theory and Applications (LATA 2016), Lecture Notes in Computer Science Volume 9618 (2016) 592-602. doi:10.1007/978-3-319-30000-9_45.
• [3] A. Ehrenfeucht, G. Rozenberg: Reaction systems. Fundamenta Informaticae 75 (2007) 263-280.
• [4] D. Genova, H.J. Hoogeboom, N. Jonoska: A Graph Isomorphism Condition and Equivalence of Reaction Systems. Theoretical Computer Science 701 (2017) 109-119. doi:10.1016/j.tcs.2017.05.019.
• [5] J. Kleijn, M. Koutny, Ł. Mikulski: Reaction Systems and Enabling Equivalence. Fundamenta Informaticae 171 (2020) 261-277. doi:10.3233/FI-2020-1882.
• [6] A. Salomaa: On State Sequences Defined by Reaction Systems. Kozen Festschrift, Lecture Notes in Computer Science Volume 7230 (2012) 271-282. doi:10.1007/978-3-642-29485-3_17.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).