Tampere University of Technology

TUTCRIS Research Portal

On constructibility and unconstructibility of LTS operators from other LTS operators

Research output: Contribution to journalArticleScientificpeer-review

Standard

On constructibility and unconstructibility of LTS operators from other LTS operators. / Valmari, Antti.

In: Acta Informatica, Vol. 52, No. 2-3, 2015, p. 207-234.

Research output: Contribution to journalArticleScientificpeer-review

Harvard

APA

Vancouver

Author

Valmari, Antti. / On constructibility and unconstructibility of LTS operators from other LTS operators. In: Acta Informatica. 2015 ; Vol. 52, No. 2-3. pp. 207-234.

Bibtex - Download

@article{3b26b4714f904d3d8af017aa042d3c38,
title = "On constructibility and unconstructibility of LTS operators from other LTS operators",
abstract = "An LTS operator can be constructed from a set of LTS operators up to an equivalence if and only if there is an LTS expression that only contains operators from the set and whose result is equivalent to the result of the operator. In this publication this idea is made precise in the context where each LTS has an alphabet of its own and the operators may depend on the alphabets. Then the extent to which LTS operators are constructible is studied. Most, if not all, established LTS operators have the property that each trace of the result arises from the execution of no more than one trace of each of its argument LTSs, and similarly for infinite traces. All LTS operators that have this property and satisfy some other rather weak regularity properties can be constructed from parallel composition and hiding up to the equivalence that compares the alphabets, traces, and infinite traces of the LTSs. Furthermore, a collection of other miscellaneous constructibility and unconstructibility results is presented.",
author = "Antti Valmari",
year = "2015",
doi = "10.1007/s00236-015-0217-2",
language = "English",
volume = "52",
pages = "207--234",
journal = "Acta Informatica",
issn = "0001-5903",
publisher = "Springer Verlag",
number = "2-3",

}

RIS (suitable for import to EndNote) - Download

TY - JOUR

T1 - On constructibility and unconstructibility of LTS operators from other LTS operators

AU - Valmari, Antti

PY - 2015

Y1 - 2015

N2 - An LTS operator can be constructed from a set of LTS operators up to an equivalence if and only if there is an LTS expression that only contains operators from the set and whose result is equivalent to the result of the operator. In this publication this idea is made precise in the context where each LTS has an alphabet of its own and the operators may depend on the alphabets. Then the extent to which LTS operators are constructible is studied. Most, if not all, established LTS operators have the property that each trace of the result arises from the execution of no more than one trace of each of its argument LTSs, and similarly for infinite traces. All LTS operators that have this property and satisfy some other rather weak regularity properties can be constructed from parallel composition and hiding up to the equivalence that compares the alphabets, traces, and infinite traces of the LTSs. Furthermore, a collection of other miscellaneous constructibility and unconstructibility results is presented.

AB - An LTS operator can be constructed from a set of LTS operators up to an equivalence if and only if there is an LTS expression that only contains operators from the set and whose result is equivalent to the result of the operator. In this publication this idea is made precise in the context where each LTS has an alphabet of its own and the operators may depend on the alphabets. Then the extent to which LTS operators are constructible is studied. Most, if not all, established LTS operators have the property that each trace of the result arises from the execution of no more than one trace of each of its argument LTSs, and similarly for infinite traces. All LTS operators that have this property and satisfy some other rather weak regularity properties can be constructed from parallel composition and hiding up to the equivalence that compares the alphabets, traces, and infinite traces of the LTSs. Furthermore, a collection of other miscellaneous constructibility and unconstructibility results is presented.

U2 - 10.1007/s00236-015-0217-2

DO - 10.1007/s00236-015-0217-2

M3 - Article

VL - 52

SP - 207

EP - 234

JO - Acta Informatica

JF - Acta Informatica

SN - 0001-5903

IS - 2-3

ER -