In the study of behaviours of concurrent systems, traces are sets of behaviourally equivalent action sequences. Traces can be represented by causal partial orders. Step traces, on the other hand,... Show moreIn the study of behaviours of concurrent systems, traces are sets of behaviourally equivalent action sequences. Traces can be represented by causal partial orders. Step traces, on the other hand, are sets of behaviourally equivalent step sequences, each step being a set of simultaneous actions. Step traces can be represented by relational structures comprising non-simultaneity and weak causality. In this paper, we propose a classification of step alphabets as well as the corresponding step traces and relational structures representing them. We also explain how the original trace model fits into the overall framework. Show less
Janicki, R.; Kleijn, H.C.M.; Koutny, M.; Mikulski, L. 2017
A query is determined by a view, if the result of the query can be reconstructed from the result of the view. We consider the problem of deciding for two given (functional) tree transformations,... Show moreA query is determined by a view, if the result of the query can be reconstructed from the result of the view. We consider the problem of deciding for two given (functional) tree transformations, whether one is determined by the other. If the view transformation is induced by a tree transducer that may copy, then determinacy is undecidable. For a large class of noncopying views, namely compositions of extended linear top–down tree transducers, we show that determinacy is decidable, where queries are either deterministic top–down tree transducers (with regular look-ahead) or deterministic MSO tree transducers. We also show that if a query is determined by a view, then it can be rewritten into a query that works over the view and is in the same class of transducers as the query. The proof relies on the decidability of equivalence for the considered classes of queries, and on their composition closure. Show less
