Sesqui-Pushout Rewriting: Concurrency, Associativity and Rule Algebra Framework

被引：12
作者：
Behr, Nicolas [1 ]
机构：
[1] Univ Paris, IRIF, CNRS, F-75013 Paris, France
来源：
ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE | 2019年 / 309期
关键词：
CATEGORIES;
D O I：
10.4204/EPTCS.309.2
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Sesqui-pushout (SqPO) rewriting is a variant of transformations of graph-like and other types of structures that fit into the framework of adhesive categories where deletion in unknown context may be implemented. We provide the first account of a concurrency theorem for this important type of rewriting, and we demonstrate the additional mathematical property of a form of associativity for these theories. Associativity may then be exploited to construct so-called rule algebras (of SqPO type), based upon which in particular a universal framework of continuous-time Markov chains for stochastic SqPO rewriting systems may be realized.
引用
收藏
页码：23 / 52
页数：30
相关论文
共 42 条
[1]  
Anderson WJ, 1991, CONTINUOUS TIME MARK, DOI [DOI 10.1007/978-1-4612-3038-0, 10.1007/978-1-4612-3038-0]
[2]  
Behr N., 2019, ARXIV
[3]  
Behr N., 2019, ARXIV
[4]  
Behr N, 2018, Arxiv, DOI arXiv:1712.06575
[5]  
Behr N, 2020, Arxiv, DOI arXiv:1904.12829
[6]   Stochastic mechanics of graph rewriting [J].
Behr, Nicolas ;
Danos, Vincent ;
Garnier, Ilias .
PROCEEDINGS OF THE 31ST ANNUAL ACM-IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2016), 2016, :46-55
[7]  
Behr Nicolas, 2018, 27 EACSL ANN C COMPU, V119, p11:1, DOI [10.4230/LIPIcs, DOI 10.4230/LIPICS]
[8]  
Behr Nicolas, 2016, ARXIV
[9]   Boson normal ordering via substitutions and Sheffer-type polynomials [J].
Blasiak, P ;
Horzela, A ;
Penson, KA ;
Duchamp, GHE ;
Solomon, AI .
PHYSICS LETTERS A, 2005, 338 (02) :108-116
[10]  
Blasiak P., 2011, Sem. Lothar. Combin., V65
12345