The paper investigates the relative expressiveness of two logic-based languages for reasoning over streams, namely LARS Programs - the language of the Logic-based framework for Analytic Reasoning over Streams called LARS - and LDSR - the language of the recent extension of the -DLV system for stream reasoning called I-DLV-sr. Although these two languages build over Datalog, they do difer both in syntax and semantics. To reconcile their expressive capabilities for stream reasoning, we define a comparison framework that allows us to show that, without any restrictions, the two languages are incomparable and to identify fragments of each language that can be expressed via the other one.
exactly the mission of the present paper. To this aim, the prime objective is to compare LDSR with one of the most famous and well-studied formalisms for reasoning over streams that goes under the name of LARS Programs (the language of LARS), where LARS is the Logic-based framework for Analytic Reasoning over Streams [8]. More precisely, the paper investigates the relative expressiveness of LDSR and LARS Programs. Despite the fact that these languages build over Datalog and represent the information via sets of ASP ground predicate atoms associated with diferent time points, unfortunately they overall difer both in syntax and semantics. In particular, LDSR associates information that is true at every time point with standard ASP facts, whereas LARS Programs involve background atoms whose truth is not directly associated with all the time points. Moreover, given an input stream, LDSR returns a single set of information related to the most recent time point (streaming model), whereas LARS Programs associate, for each diferent time point of the stream, another stream called answer stream at that time point.
To reconcile the expressive capabilities for stream reasoning of LDSR and LARS Programs, we first define a comparison framework that allows to understand in which cases, starting from the same input stream, both languages may produce the same output. Inside this framework, we identify three output profiles —called atomic, bound, and full— that fix the form of the output stream. Without any restriction on the two languages, the paper shows that they are incomparable under all the output profiles. Eventually, for each output profile, the paper isolates large fragments of each of the two languages that can be expressed via the other one.
We assume to have finite sets , , and consisting of variables, constants, predicate names and respectively; we constrain and to be disjoint. A term is either a variable in or a constant in . A predicate atom has the form (1, . . . , ), where ∈ is a predicate name, 1, . . . , are terms and ≥ 0 is the arity of the predicate atom; a predicate atom () of arity 0 can be also denoted by . A predicate atom is ground if none of its terms is a variable. We denote by the set of all ground predicate atoms constructible from predicate names in and constants in . We divide the set of predicates into two disjoint subsets, namely the extensional predicates and the intensional predicates . Extensional predicates are further partitioned into for background data and for data streams. The mentioned partitions are analogously defined for ground atoms , and . In what follows we will introduce diferent types of constructs peculiar to the two languages considered in this paper. In both, given a set of constructs , we will denote by () the set of predicates appearing in .
A stream Σ is a sequence of sets of ground predicate atoms ⟨0, . . . , ⟩ such that for 0 ≤ ≤ , ⊆ . Each natural number is called time point. A ground predicate atom ∈ is true at the -th time point. Given a value ∈ N s.t. 0 ≤ ≤ , we define the restriction of Σ to the stream ⟨0, . . . , ⟩ denoted with Σ| . Moreover, let ⊆ we indicate with Σ| the stream ⟨0′, . . . , ′⟩ with ′ = ⋃︀{∈|()∈ } for each ∈ {0, . . . , }. A subset of a stream Σ = ⟨0, . . . , ⟩ is a stream Σ′ = ⟨0′, . . . , ′⟩ such that ′ = ∅ for each ̸∈ (Σ′) where (Σ′) is a subset of consecutive numbers of the set {0, . . . , } and for each ∈ (Σ′) ′ ⊆ . For a stream Σ = ⟨0, . . . , ⟩, a backward observation identifies ground predicate atoms that are true at some time points preceding the -th time point. More formally, given a stream Σ = ⟨0, . . . , ⟩ and a set of numbers ⊂ N, we define the backward observation of Σ w.r.t. as the family of sets { | = − with ∈ ∧ ≥ 0}, and we denote it as (Σ, ). Given ∈ N, a backward observation of Σ w.r.t. {0, . . . , } is called window.
A window function is a function that returns, given a stream Σ and a time point ∈ {1, ..., }, a substream of Σ. We consider only time-based window functions, which select all the atoms appearing in the last time points, to which a window is trivially associated according to the definition above. Given a predicate atom , a term ∈ ∪ and a window function , formulas are defined by the following grammar:
::= | ¬ | ∧ | ∨ | → | ◇ | □ | @ | ⊞ | ◁ .
A LARS program P is a set of rules of the form ← 1, . . . , , where , 1, . . . , are formulas. Given a rule , we call the head of , denoted with (), and we call the conjunction 1 ∧ · · · ∧ the body of , denoted with (). A ground formula can be satisfied at a time point in a that is a triple = (Σ, , ) where Σ is a stream, is a set of window functions and ⊆ . Let Σ′ ⊆ Σ, we start defining the entailment relation ⊩ between (, Σ′, ) and formulas: • , Σ′, ⊩ if ∈ or ∈ • , Σ′, ⊩ ¬ if , ⊮ • , Σ′, ⊩ ∧ if , ⊩ and , ⊩ • , Σ′, ⊩ ∨ if , ⊩ or , ⊩ • , Σ′, ⊩ → if , ⊮ or , ⊩ • , Σ′, ⊩ ◇ if , Σ′, ⊩ for some ′ ∈ (Σ′) • , Σ′, ⊩ □ if , Σ′, ⊩ for all ′ ∈ (Σ′) , • , Σ′, ⊩ @′ if , Σ′, ′ ⊩ and ′ ∈ (Σ′) , • , Σ′, ⊩ ⊞ , if , Σ′′, ⊩ where Σ′′ = (Σ′, ), • , Σ′, ⊩ ◁ if , Σ, ⊩ .
The structure = (Σ, , ) satisfies at time (, |= ) if , Σ′, ⊩ . Given a ground LARS program , a stream Σ and a structure we say that: () is a model of rule ∈ for at time , denoted , |= , if , |= () → (); () is a model of for at time , denoted , |= , if , |= for all rules ∈ ; () is a minimal model, if no model ′ = (Σ′, , ) of for at time exists such that Σ′ ⊂ Σ and (Σ) = (Σ′); and () The reduct of a program with respect to at time is defined by , = { ∈ |, |= ()}. Fixed an input stream , contains only atoms belong to , we call any stream Σ such that all atoms that occur in Σ but not in have intensional predicates. An interpretation stream Σ for a stream is an of a program , if = (Σ, , ) is a ⊆ -minimal model of the reduct , for at time . The semantics of the non-ground programs is given by the answer streams of according groundings, obtained by replacing variables with constants from , respectively time points from (Σ), in all possible ways. We consider LARS programs with a single answer stream for each time point, denoted with LARSD, and we indicate the single answer stream of for at with (, , ). at least in {1, . . . , } |{ ∈ (Σ, ) : ∈ }| ≥ |{ ∈ (Σ, ) : ∈ }| < always in {1, . . . , } count in {1, . . . , } ∀ ∈ (Σ, ), ∈
∃ ∈ (Σ, ) : ̸∈ |{ ∈ (Σ, ) : ∈ }| = |{ ∈ (Σ, ) : ∈ }| ̸=
non-empty set = {1, . . . , } ⊂ N, we define three types of streaming atoms: Given a predicate atom , a term ∈ ∩ N+, a counting term ∈ ( ∩ N+) ∪ , and a finite at least in {1, . . . , } | always in {1, . . . , } | count in {1, . . . , } In particular, if is of the form {0, ..., }, then this set can be alternatively written as [] inside streaming atoms; also we may write in place of at least 1 in [0]. A streaming atom (resp., not ) is said to be a positive streaming literal (resp., negative streaming literal), where not denotes negation as failure. A streaming literal is said to be harmless if it has form at least in or always in ; otherwise, it is said to be non-harmless. A streaming literal is said to be ground if none of its terms is a variable.
A rule is a formula of form (
0 and 1, . . . , represent a conjunction of literals (streaming literals or (false) at time point . streaming literal of () also appear in a positive streaming literal of ().
For a rule , we say that the head of is the set () = {}, whereas the set () = {1, . . . , } is referred to as the body of . A rule is safe if all variables in () or in a negative
A program is a finite set of safe rules. We denote with form(
A program is stratified if there is a partition of disjoint sets of rules = Π1 ∪ · · · ∪ Π Π1, . . . , Π. An LDSR program is a program being also stratified. literal in the body of a rule in Π with predicate , { ∈ |() = {(1, . . . , )}} ⊆ (called strata) such that for ∈ {1, . . . , } both these conditions hold: () for each harmless ⋃︀ =1 Π ; {(1, . . . , )}} ⊆ () for each non-harmless literal in the body of a rule in Π with predicate , { ∈ |() = ⋃︀− =11 Π . We call Π1, . . . , Π a stratification for and is stratified by
A backward observation allows to define the truth of a ground streaming literal at a given time point. Given a stream Σ = ⟨0, . . . , ⟩, = {1, . . . , } ⊂ N, ∈ ∖ {0} and the backward observation (Σ, ), Table 1 reports when Σ entails a ground streaming atom (denoted Σ |= ) or its negation (Σ |= not ). If Σ |= ( Σ |= not ) we say that is true
To make a comparison between LARSD and LDSR, we defined also for LDSR a model-theoretic semantics that can be shown to be equivalent to the operational semantics originally defined. Moreover, besides the concept of streaming model for LDSR, we defined the concept of answer stream.
Consider an LDSR program . Given a rule ∈ , the ground instantiation () of
denotes the set of rules obtained by applying all possible substitutions from the variables in
to elements of . In particular, to the counting terms are applied only constants belong to
∩ N+. Similarly, the ground instantiation ( ) of is the set ⋃︀∈ (). Given a ground
rule ∈ , a stream Σ = ⟨0, . . . , ⟩ and a stream Σ′ = ⟨0′, . . . , ′⟩ such that Σ ⊆ Σ′, we
say that Σ′ is a model of for Σ, denoted Σ′ |= , if Σ′ |= () when Σ′ |= (). We say that
Σ′ is a model of for Σ, denoted Σ′ |= , if Σ′ |= for all rules ∈ ( ). Moreover, Σ′ is a
minimal model, if no model Ω of exists such that Ω ⊂ Σ′ and (Ω) = (Σ′). Let Σ′ be a model
of for Σ, an atom ∈ ′ is temporary in Σ′ if ̸∈ and there exists no rule ∈ form(
Note that, diferently from LARS, for which the information associated with each time point is entirely derived at the time point of evaluation, for LDSR, each time point in the answer stream is associated with the information derived when the time point has been evaluated. In other words, the answer stream for LDSR is obtained by collecting the results of the previous time points and integrating them with the result of the time point of evaluation.
In this section, we present the framework that has been designed for comparing the languages LARSD and LDSR. The comparison focuses on diferent parts of the answer stream. In particular, given an input stream = ⟨0, . . . , ⟩, when referring to an evaluation time point ≤ , one could compare the answer streams only at , or in all the time points up to or also in all time points up to . To this aim, we define three types of streams. Given ∈ N and ∈ {0, . . . , }, we say that a stream = ⟨0, . . . , ⟩ is of - if = ∅ for each ∈ {0, . . . , } ∖ {}; - if = ∅ for each ∈ { + 1, . . . , }; and -full if may be nonempty for each ∈ {0, . . . , }.
Consider a language ∈ {LDSR, LARSD}, an input stream = ⟨0, . . . , ⟩, a set of ground predicate atoms ⊆ and a program ∈ , we call (, , ) an -tuple. According to the three types of streams, for a -tuple and for each time point ∈ {0, . . . , }, we now define three types of output streams for each language .
Given a LDSR- (, , ) and a time point ∈ {0, . . . , }, we define: • -(, , ) = ⟨0, . . . , ⟩ where = ∅ for ̸= and is the streaming model of ∪ {.| ∈ } on | = ⟨0, . . . , ⟩. • -(, , ) = ⟨0, . . . , ⟩, where ⟨0, . . . , ⟩ is the answer stream of ∪ {.| ∈ } for | = ⟨0, . . . , ⟩ and = ∅ for < ≤ . • -full (, , ) = ⟨0, . . . , ⟩ where ⟨0, . . . , ⟩ is the answer stream of ∪ {.| ∈ } for | = ⟨0, . . . , ⟩ and = ∪ for < ≤ .
Analogously, given a LARSD- (, , ) and a time point ∈ {0, . . . , }, and the answer stream (, , ) = ⟨0, . . . , ⟩, we define: • -(, , ) = ⟨0, . . . , ⟩ where = ∅ for ̸= and = ∪ . • -(, , ) = ⟨0, . . . , ⟩, where = ∪ for 0 ≤ ≤ and = ∅ for < ≤ .
• -full (, , ) = ⟨0, . . . , ⟩ where = ∪ for 0 ≤ ≤ .
We now define when a fragment of a language can be expressed in the other one in our framework. In particular, we diferentiate expressible fragments from strictly expressible fragments. Given a stream form ∈ {, , full },and 1, 2 ∈ {LDSR, LARSD} with 1 ̸= 2, a fragment ⊂ 1 is - via 2 if there exists a mapping : → 2 such that, for each -tuple (, , ) and for each time point of evaluation ∈ {0, . . . , }, it holds that -(, , ) = -(, , ( ))|( ∪∪) ; moreover, is - via 2 if -(, , ) = -(, , ( )). Basically, for the non strict expressiveness, a translation into the other language is possible but it can involve the addition of auxiliary predicates, while for the strict one, there is a translation that does not require auxiliary predicates and thus for which the outputs coincide without the need of any filtering.
We are now ready to compare the two languages. The first result of the comparison is that, without any restrictions, the two languages are incomparable. The following two propositions describe the results. The ideas behind the formal demonstrations, which are instead reported in Appendix B [20], are also introduced.
Proposition 1. LARSD is not - via LDSR.
To see this, consider the simple LARSD program 1={@ − 1 ← @ .}. This program, that expresses that the presence of an atom in a time point infers the presence of an atom in the previous time point, is not expressible in LDSR since in its semantic the information associated at every time point are relative only to the information received and inferred up to it. Proposition 2. LDSR is not - via LARSD.
To prove this result, consider the following LDSR program 2 = {( ) : - (), (, ).} where the predicate belongs to the input predicates . The program 2 is not expressible in LARSD since its semantics avoids to infer ground atoms over input predicates.
Since -(, , ) ̸= -(, , ( )) implies -(, , ) = -(, , ( )) holds for ∈ {, full }, Proposition 1 and 2 imply the following result.
strictly not strictly strictly not strictly
Given the incomparability of the languages, we introduced some restrictions to identify fragments of a language expressible in the other. Up to now, we identified seven fragments that are described in detail in sections 3.1 and 3.2. Here, we briefly discuss their relations and expressiveness (see Fig. 1 and Tables 2 and 3). In particular, Table 2 presents the fragments of LARSD 1, 2 and 3. All of them are strictly expressible via LDSR. 1 is the largest identified fragment and it is atomic-expressible; 2 is obtained from 1 by imposing some restriction and it is bound-expressible, while 3 is obtained by further restricting 2, and allows for achieving full-expressivity.
As for LDSR, Table 3 summarizes its identified fragments 4,5,6 and 7. The largest fragment is 4, which is bound-expressible via LARSD; the fragment 5, that restricts 4, allows full expressiveness; the other two fragments allows for strictly expressiveness: 6 further restricts 5, and it is full-expressible, while 7 is obtained by imposing restrictions on 4 and is bound-expressible. 3.1. LARSD to LDSR Here we present the identified fragments of LARSD. We consider two types of rules: ( ) □ ( ← 1 ∧ · · · ∧ ) and (II ) ← 1, . . . , for ∈ {1, . . . , }. For a rule of type (), we denote as () the consequent {} of the implication, and with () the set of formulas { 1, . . . , } in the premise; moreover, for a rule of type (II ), we denote with ℎ() the atom {} and with () the set of formulas { 1, . . . , }. Let be a LARSD program, we denote with ( ) the set of rules of of type () and with II ( ) the set of rules of of type (II ).
We say that a predicate is marked if there are two rules ∈ ( ) and ′ ∈ II ( ) with = (()), ℎ ∈ (()) and ℎ = (ℎ(′)). The set of marked predicates of a program is denoted with ( ).
Consider a LARSD program containing rules of type () and (II ) only. Let 1 =
( ) and 2 = II ( ). We define the graph ( ) = ⟨, ⟩, where: (
tions: () = ( ) ∪ II ( ); () ∪∈ ( )(()) ∩ ( ) = ∅; () ∪∈II ( )(()) ∩ ( ) = ∅; () no cycle in ( ) contains an arc labeled with “-". Roughly, 1 contains only programs that are stratified w.r.t negation, featuring only rules of types (I) and (II), where no marked predicate appears in premises and in bodies.
Indeed, it can be shown that there is a mapping 1 : 1 → LDSR such that for each 1-
(, , ) and for each time point of evaluation ∈ {0, . . . , }, it holds that -(, , ) =
-(, , 1( )). In particular, given a program ∈ 1, the LDSR program 1( ) is
obtained by replacing:
- each rule □ ( ← 1, . . . , ) of type () with the LDSR rule : - ( 1), . . . , ( ) of
form (
Now, we define the fragment 2 that imposes an additional restriction w.r.t to 1, and the fragment 3 that further restricts 2.
condition (⋃︀∈II ( ) (ℎ())) ∩ ((⋃︀∈ ( ) (()) = ∅.
It can be shown that for the mapping 2 = 1|2 , it holds that for each 2- (, , ) and for each time point of evaluation ∈ {0, . . . , }, -(, , ) = -(, , 2( )). Basically, the additional condition for fragment 2 avoids that a temporary information associated to a time point can generate a permanent information.
We now show an example of a program belonging to fragment 2 and its image with respect to the function 2. The example is taken from one of the tasks of the “model and solve” Stream Reasoning Hackathon 2021 [21]. The task concerns urban trafic management. Trafic is observed from a top-down, third-person perspective, and vehicle movement flows in a given road network coded as Datalog facts are considered. We want to identify the vehicles that appear or disappear in the network. It is then necessary to note vehicles that were absent at the previous time point and are now present and vice versa. A rule of type () is used to evaluate the presence of vehicles at the current and previous time points; then the obtained information is used in a rule of type (II ) that detects the appearance or disappearance of a vehicle at the evaluation time point. This task can be modelled via the following program in 2: □ ( ( ℎ) ← ( ℎ, , )). ( ℎ) ← ( ℎ, , ), ¬ ⊞ 0 @ ⊤ ∧ @ − 1 ( ℎ). ( ℎ) ← ⊞ 0@ ⊤ ∧ @ − 1 ( ℎ), ¬ ( ℎ). The corresponding LDSR program, image of the 2 function, is:
( ℎ) : - ( ℎ, , ). #temp ( ℎ) : - ( ℎ, , ), not ( ℎ) in {1}. #temp ( ℎ) : - ( ℎ, , ) in {1}, not ( ℎ).
condition = II ( ).
Similarly to 2, it can be shown that, considering the mapping 3 = 1|3 , it holds that that for
each 3- (, , ) and for each time point of evaluation ∈ {0, . . . , }, -full (, , ) =
-full (, , 3( )). Intuitively, since in LDSR the evaluation of a program with respect to a
time point can not add information in the output stream at time points that are subsequent to
, to achieve full expressiveness, we impose the restriction to rules of type type (II ) in LARSD
as these are evaluated only at and do not change the output in the subsequent time points.
3.2. LDSR to LARSD
Here we present the identified fragments of LDSR along with their expressiveness. While, for
the fragments of LARSD we obtained strict expressiveness and each rule in LARSD has been
translated into exactly one rule in LDSR, for the fragments of LDSR, the translation, in general,
needs auxiliary atoms and additional rules to simulate the behavior of rules of the form (
The largest identified fragment is 4 that is defined as follows.
⋃︀∈ (()) ⊂ .
Basically, 4 is obtained from LDSR by simply imposing that no extensional predicate appears in the head of a rule.
It can be shown that there is a mapping 4 : 4 → LARSD such that for each 4- (, , ) and for each ∈ {0, . . . , }, -(, , ) = -(, , 4( ))|( ∪∪) . First, we note that, in general, each streaming atom in 4 has to properly translated into a LARSD formula; moreover a special rewriting, requiring additional rules, has to be performed for streaming atoms of the form count in {1, . . . , }, where is a variable in and for all the aggregate atoms. Thus, without going into details, the mapping 4 relies on a function that associates each streaming atom (but those of form count in {1, . . . , }) with a LARSD formula that expresses the condition that must be satisfied in the stream for the streaming atom to be true; moreover, if is an aggregate atom or a streaming atom of the form count in {1, . . . , }, associates it with a formula containing auxiliary atoms defined via an additional set of rules that are needed to simulate its semantics. For the sake of the presentation, the function and the set of additional rules are reported in Appendix A.1 [20].
Furthermore, given a program ∈ 4, the mapping 4 has to replace each rule in with
one or more LARSD rules. In sum, the program 4( ) is obtained by:
- replacing each rule : - 1, . . . , of form (
Basically, the mapping 4 manages the interaction between the two forms of rules, simulating,
at an evaluation time point , the temporary derivations obtained in the previous time points
and evaluating their efect on the permanent derivations that will be part of the output. This
is mainly obtained by creating and handling a copy of each rule of the form (
We are now ready to define the fragment 5 that is obtained from 4 by avoiding rules of
form (
= form2( ).
Proposition 7. 5 is full - via LARSD.
To see this, consider, the mapping 5 : 5 → LARSD such that, for each program ∈ 5, 5( )
is obtained by:
- replacing each rule #temp : - 1, . . . , of form (
It can be shown that 5 is such that for each 5- (, , ) and for each ∈ {0, . . . , },
-full (, , ) = -full (, , 5( ))|( ∪∪) . Roughly, similarly to 4, 5 relies on a
function ′ for rewriting body atoms and adds auxiliary rules for handling aggregate atoms or a
streaming atoms of the form count in {1, . . . , } (more details on this are reported in
Appendix A.2 [20]); however the translation for the fragment 5 is simpler than the one for
4, as it is suficient to associate each rule of form (
The fragment 6 restrict 5 to reach strict full expressiveness.
atoms of the form count in {1, . . . , } where ∈ and aggregate atoms are not allowed in rule bodies.
It can be shown that for the mapping 6 = 5|6 , it holds that for each 6- (, , ) and for each ∈ {0, . . . , }, -full (, , ) = -full (, , 6( )). Since no atoms involving the addition of auxiliary predicates are considered, 6 is strictly expressible.
The last considered fragment 7 still features strict expressiveness, but of bound type, as,
diferently from 6, it allows also rules of form (
conditions: () (∪∈form2( )((()))∩(∪∈form2 (P)((())) = ∅ () streaming atoms of the form count in {1, . . . , } where ∈ and aggregate atoms are not allowed in rule bodies.
It can be shown that there is a mapping 7 : 7 → LARSD such that for each 7- (, , )
and for each ∈ {0, . . . , }, -(, , ) = -(, , 7( )). To see this, consider,
the mapping 7 : 7 → LARSD such that, for each program ∈ 7, 7( ) is obtained by:
- replacing each rule #temp : - 1, . . . , of form (
Definition 9. Given an atom (1, . . . , ) and a LDSR rule with () = (′1, . . . , ′)
we call definition of (1, . . . , ) in , denoted with ((1, . . . , )), the conjunction
⋀︀{ ∈()} ⋀︀1≤ ≤ = ′. Given an LDSR program the definition of (1, . . . , ) in
is ((1, . . . , )) = (1, . . . , ) ∨ (⋁︀{∈ |(())=} ((1, . . . , ))).
This definition identifies, for each predicate in the head of a rule of form (
Consider, for example, the LDSR program ′ that could be used for monitoring irregularity in a subway station monitoring system. Three minutes are expected to elapse between the arrival of one train and the next, so the program records an irregularity when one train passes and another has already passed in one of the previous two minutes: ′ = { : - _, _ at least 1 in {1, 2}.} The program belongs to the 7 fragment, and the corresponding LARSD program with respect to the 7 function is as follows: 7( ′) = {□ ( ← ⊞ 0@ ⊤ ∧ (@1 _ ∧ 1 = − 0)
∧ (@2 _ ∧ ((2 = − 1) ∨ (2 = − 2))).}
This work presents a formal comparison about the relative expressiveness of the two languages LDSR and LARS. The main contribution of the work is twofold: () we propose a suitable framework to compare the two languages, which exhibit diferent syntax and semantics. and () for each language, we identify a number of fragments that can be expressed by the other one, showing possible rewritings. In order to compare the semantics of the two languages, we ifrst provided an alternative equivalent model-theoretic definition of the semantics of LDSR, instead of the operational one originally provided. Moreover, we defined the concept of answer stream also for LDSR, as an extension of the streaming model. The framework allowed us for focusing the comparison on diferent forms of the output stream (atomic, bound, full) and on the nature of the rewriting that could forbid or admit the addition of auxiliary predicates (strict or not strict expressiveness, respectively). For each given form of output and type of rewriting, we studied how to build fragments of a language that could meet the desired expressiveness. To do this, we considered the semantics behind each construct or combination of constructs that can occur in the rules and the efect of interactions between the diferent rules. The fragments 1, ..., 7 are the largest we identified so far, but, of course, these could be further enlarged and new ones could be possibly found; this will be the subject of future works.
This work has been partially supported by the project “MAP4ID - Multipurpose Analytics Platform 4 Industrial Data”, N. F/190138/01-03/X44 and by the Italian MIUR Ministry and the Presidency of the Council of Ministers under the project “Declarative Reasoning over Streams" under the “PRIN" 2017 call (CUP 2417000080001, project 2017M9C25L_001).