Difference between revisions of "Publications/fahrenberg.22.iandc"
From LRDE
(Created page with "{{Publication | published = true | date = 2022-06-30 | authors = Uli Fahrenberg, Christian Johansen, Georg Struth, Krzysztof Ziemianski | title = Posets With Interfaces as a M...") |
|||
(4 intermediate revisions by the same user not shown) | |||
Line 2: | Line 2: | ||
| published = true |
| published = true |
||
| date = 2022-06-30 |
| date = 2022-06-30 |
||
− | | authors = Uli Fahrenberg, Christian Johansen, Georg Struth, Krzysztof |
+ | | authors = Uli Fahrenberg, Christian Johansen, Georg Struth, Krzysztof Ziemiański |
| title = Posets With Interfaces as a Model for Concurrency |
| title = Posets With Interfaces as a Model for Concurrency |
||
| journal = Information and Computation |
| journal = Information and Computation |
||
Line 15: | Line 15: | ||
| lrdenewsdate = 2022-06-30 |
| lrdenewsdate = 2022-06-30 |
||
| lrdeprojects = AA |
| lrdeprojects = AA |
||
− | | abstract = We introduce posets with interfaces (iposets) and generalise their standard serial composition to a new gluing composition. |
+ | | abstract = We introduce posets with interfaces (iposets) and generalise their standard serial composition to a new gluing composition. In the partial order semantics of concurrency, interfaces and gluing allow modelling events that extend in time and across components. Alternativelytaking a decompositional view, interfaces allow cutting through events, while serial composition may only cut through edges of a poset. We show that iposets under gluing composition form a category, which generalises the monoid of posets under serial composition up to isomorphism. They form a 2-category when a subsumption order and a lax tensor in the form of a non-commutative parallel composition are added, which generalises the interchange monoids used for modelling series-parallel posets. We also study the gluing-parallel hierarchy of iposets, which generalises the standard series-parallel one. The class of gluing-parallel iposets contains that of series-parallel posets and the class of interval orders, which are well studied in concurrency theory, too. We also show that it is strictly contained in the class of all iposets by identifying several forbidden substructures. |
| type = article |
| type = article |
||
| id = fahrenberg.22.iandc |
| id = fahrenberg.22.iandc |
||
Line 22: | Line 22: | ||
@Article<nowiki>{</nowiki> fahrenberg.22.iandc, |
@Article<nowiki>{</nowiki> fahrenberg.22.iandc, |
||
author = <nowiki>{</nowiki>Uli Fahrenberg and Christian Johansen and Georg Struth and |
author = <nowiki>{</nowiki>Uli Fahrenberg and Christian Johansen and Georg Struth and |
||
− | Krzysztof |
+ | Krzysztof Ziemia<nowiki>{</nowiki>\'n<nowiki>}</nowiki>ski<nowiki>}</nowiki>, |
title = <nowiki>{</nowiki>Posets With Interfaces as a Model for Concurrency<nowiki>}</nowiki>, |
title = <nowiki>{</nowiki>Posets With Interfaces as a Model for Concurrency<nowiki>}</nowiki>, |
||
journal = <nowiki>{</nowiki>Information and Computation<nowiki>}</nowiki>, |
journal = <nowiki>{</nowiki>Information and Computation<nowiki>}</nowiki>, |
||
− | volume = |
+ | volume = 285, |
number = <nowiki>{</nowiki>B<nowiki>}</nowiki>, |
number = <nowiki>{</nowiki>B<nowiki>}</nowiki>, |
||
− | pages = |
+ | pages = 104914, |
− | year = |
+ | year = 2022, |
+ | month = may, |
||
url = <nowiki>{</nowiki>https://doi.org/10.1016/j.ic.2022.104914<nowiki>}</nowiki>, |
url = <nowiki>{</nowiki>https://doi.org/10.1016/j.ic.2022.104914<nowiki>}</nowiki>, |
||
doi = <nowiki>{</nowiki>10.1016/j.ic.2022.104914<nowiki>}</nowiki>, |
doi = <nowiki>{</nowiki>10.1016/j.ic.2022.104914<nowiki>}</nowiki>, |
||
Line 44: | Line 45: | ||
composition form a category, which generalises the monoid |
composition form a category, which generalises the monoid |
||
of posets under serial composition up to isomorphism. They |
of posets under serial composition up to isomorphism. They |
||
− | form a |
+ | form a 2-category when a subsumption order and a lax tensor |
− | + | in the form of a non-commutative parallel composition are |
|
− | + | added, which generalises the interchange monoids used for |
|
− | + | modelling series-parallel posets. We also study the |
|
− | + | gluing-parallel hierarchy of iposets, which generalises the |
|
− | + | standard series-parallel one. The class of gluing-parallel |
|
− | + | iposets contains that of series-parallel posets and the |
|
− | + | class of interval orders, which are well studied in |
|
− | + | concurrency theory, too. We also show that it is strictly |
|
− | + | contained in the class of all iposets by identifying |
|
− | + | several forbidden substructures.<nowiki>}</nowiki> |
|
<nowiki>}</nowiki> |
<nowiki>}</nowiki> |
||
Latest revision as of 13:41, 27 October 2022
- Authors
- Uli Fahrenberg, Christian Johansen, Georg Struth, Krzysztof Ziemiański
- Journal
- Information and Computation
- Type
- article
- Projects
- AA"AA" is not in the list (Vaucanson, Spot, URBI, Olena, APMC, Tiger, Climb, Speaker ID, Transformers, Bison, ...) of allowed values for the "Related project" property.
- Date
- 2022-06-30
Abstract
We introduce posets with interfaces (iposets) and generalise their standard serial composition to a new gluing composition. In the partial order semantics of concurrency, interfaces and gluing allow modelling events that extend in time and across components. Alternativelytaking a decompositional view, interfaces allow cutting through events, while serial composition may only cut through edges of a poset. We show that iposets under gluing composition form a category, which generalises the monoid of posets under serial composition up to isomorphism. They form a 2-category when a subsumption order and a lax tensor in the form of a non-commutative parallel composition are added, which generalises the interchange monoids used for modelling series-parallel posets. We also study the gluing-parallel hierarchy of iposets, which generalises the standard series-parallel one. The class of gluing-parallel iposets contains that of series-parallel posets and the class of interval orders, which are well studied in concurrency theory, too. We also show that it is strictly contained in the class of all iposets by identifying several forbidden substructures.
Documents
Bibtex (lrde.bib)
@Article{ fahrenberg.22.iandc, author = {Uli Fahrenberg and Christian Johansen and Georg Struth and Krzysztof Ziemia{\'n}ski}, title = {Posets With Interfaces as a Model for Concurrency}, journal = {Information and Computation}, volume = 285, number = {B}, pages = 104914, year = 2022, month = may, url = {https://doi.org/10.1016/j.ic.2022.104914}, doi = {10.1016/j.ic.2022.104914}, timestamp = {Tue, 28 Jun 2022 21:08:18 +0200}, biburl = {https://dblp.org/rec/journals/iandc/FahrenbergJSZ22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, abstract = {We introduce posets with interfaces (iposets) and generalise their standard serial composition to a new gluing composition. In the partial order semantics of concurrency, interfaces and gluing allow modelling events that extend in time and across components. Alternatively, taking a decompositional view, interfaces allow cutting through events, while serial composition may only cut through edges of a poset. We show that iposets under gluing composition form a category, which generalises the monoid of posets under serial composition up to isomorphism. They form a 2-category when a subsumption order and a lax tensor in the form of a non-commutative parallel composition are added, which generalises the interchange monoids used for modelling series-parallel posets. We also study the gluing-parallel hierarchy of iposets, which generalises the standard series-parallel one. The class of gluing-parallel iposets contains that of series-parallel posets and the class of interval orders, which are well studied in concurrency theory, too. We also show that it is strictly contained in the class of all iposets by identifying several forbidden substructures.} }