Series and parallel operations on pomsets

DOI10.1007/3-540-46691-6_25MaRDI QIDQ4501680zbMATH OpenFDO

Authors Satoshi Okawa, Zoltán Ésik

Publication date 23 April 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-46691-6_25

zbMATH Keywords

finitely generated varietyfree algebramultisorted algebrasemantics

Mathematics Subject Classification ID

Partial orders, general (06A06) Heterogeneous algebras (08A68) Applications of universal algebra in computer science (08A70) Products, amalgamated products, and other kinds of limits and colimits (08B25) Axiomatic model classes (08C10)

Review text

Let \(A\) be a set. The two-sorted algebra \(\mathbf P\mathbf o\mathbf m\) formed by the sets of isomorphism classes of finite posets labeled by \(A\) and isomorphism classes of infinite countable posets labeled by \(A\) endowed by two binary operations modelling series and/or parallel products and two unary operations modelling infinitary power of binary operations is defined. The subalgebra \(\mathbf S\mathbf p(A)\) of \(\mathbf P\mathbf o\mathbf m\) generated by one-element posets labeled by elements of \(A\) is relatively free as well as the subalgebra \(\mathbf S\mathbf p(B_1,B_2)\) of \(\mathbf P \mathbf o\mathbf m\) generated by one-element posets labeled by elements of \(B_1\) and by infinite powers of one-element posets labeled by elements of \(B_2\) where \(B_1\) and \(B_2\) are disjoint sets with \(A=B_1\cup B_2\). The variety generated by \(\mathbf S\mathbf p(A)\) or \(\mathbf S\mathbf p(B_1,B_2)\) is not finitely generated but there exists a polynomial time algorithm deciding whether a given identity is satisfied in this variety. For the entire collection see [Zbl 0931.00044].

Recommendations

• Algebra and theory of order-deterministic pomsets
• Varieties generated by languages with poset operations
• The equational theory of pomsets

Cited in

(6)

• CCS with Hennessy's merge has no finite-equational axiomatization
• Varieties generated by languages with poset operations
• Algebraic and graph-theoretic properties of infiniten-posets
• Equational Theories of Scattered and Countable Series-Parallel Posets
• Generating Posets Beyond N
• The quest for equational axiomatizations of parallel composition: status and open problems

This page was built for publication: Series and parallel operations on pomsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4501680)