Tampere University of Technology

TUTCRIS Research Portal

On constructibility and unconstructibility of LTS operators from other LTS operators

Research output: Contribution to journalArticleScientificpeer-review


Original languageEnglish
Pages (from-to)207-234
Number of pages28
JournalActa Informatica
Issue number2-3
Publication statusPublished - 2015
Publication typeA1 Journal article-refereed


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.

Publication forum classification

Field of science, Statistics Finland

Downloads statistics

No data available