ABSTRACT. We present a formal model for event-processing pipelines. Event-processing pipelines appear in a large number of domains, from control of cyber-physical systems (CPS), to large scale data analysis, to Internet-of-things applications. These applications are characterized by stateful transformations of event streams, for example, for the purposes of sensing, computation, and actuation of inner control loops in CPS applications, and for data cleaning, analysis, training, and querying in data analytics applications. Our formal model provides two abstractions: streams of data, and stateful, probabilistic, filters, which transform input streams to output streams probabilistically. Programs are compositions of filters. The filters are scheduled and run by an explicit, asynchronous, scheduler. We provide a transition system semantics for such programs based on infinite-state Markov decision processes. We characterize when a program is scheduler-independent, that is, provides the same observable behavior under every scheduler, based on local commutativity.

ABSTRACT. There exist powerful techniques to infer upper bounds on the innermost runtime complexity of term rewrite systems (TRSs), i.e., on the lengths of rewrite sequences that follow an innermost evaluation strategy. However, the techniques to analyze the (full) runtime complexity of TRSs are substantially weaker. In this paper, we present a sufficient criterion to ensure that the runtime complexity of a TRS coincides with its innermost runtime complexity. This criterion can easily be checked automatically and it allows to use all techniques and tools for innermost runtime complexity in order to analyze (full) runtime complexity. By extensive experiments with an implementation of our results in the tool AProVE, we show that this improves the state of the art of automated complexity analysis significantly.

ABSTRACT. We design a new theory of higher order functions that is well-suited for the complexity analysis of a standard higher order functional language à la ML. We manage to express the interpretation of a given program in terms of a least fixpoint and we show that when restricted to functions bounded by higher order polynomials, they characterize exactly classes of tractable functions known as Basic Feasible Functions at any order.

ABSTRACT. In this paper, we propose a new approach for defining tractable classes in propositional satisfiability problem (in short SAT). The basic idea consists in transforming SAT instances into instances of the problem of finding a maximum independent set. In this context, we only consider propositional formul\ae{} in conjunctive normal form where each clause is either positive or binary negative. Tractable classes are obtained from existing polynomial time algorithms of the problem of finding a maximum independent set in the case of different graph classes, such as claw-free graphs and perfect graphs. We show, in particular, that the pigeonhole principle belongs to one of the defined tractable classes. Furthermore, we propose a characterization of the minimal models in the largest considered fragment based on the maximum independent set problem.

ABSTRACT. We propose a rewriting modulo approach to define parallel transformation of graph structures in the context of overlapping graph rewrite systems. As parallel transformation of a graph does not produce a graph in general, we propose first some sufficient conditions that ensure the closure of graphs by parallel rewrite relations. Then we mainly introduce and discuss two parallel rewrite relations over graphs. The first relation is functional and thus deterministic, the other one is not functional in general. We propose sufficient conditions under which the second relation is deterministic.

ABSTRACT. Partial Model-Checking (PMC) is an efficient tool to reduce the combinatorial explosion of a state-space, arising in the verification of loosely-coupled software systems. At the same time, it is useful to consider quantitative temporal-modalities, where a weight represents a level of satisfaction for their verification. This allows for checking whether satisfying such a desired modality is too much costly, by comparing the final score to a given threshold. We stir these two ingredients together in order to provide a Quantitative PMC function (QPMC), based on the algebraic structure of semirings. We design a method to extract part of the weight during QPMC, with the purpose to avoid the evaluation of a modality as soon as the threshold is crossed. Moreover, we extend classical heuristics to be quantitative, and we investigate the complexity of QPMC.

ABSTRACT. Simultaneous occurrences of multiple recurrence relations in a system of non-linear constrained Horn clauses are crucial for proving its satisfiability. A solution of such system is often inexpressible in the constraint language. We propose to synchronize recurrent computations, thus increasing the chances for a solution to be found. We introduce a notion of CHC product allowing to formulate a lightweight iterative algorithm of merging recurrent computations into groups and prove its soundness. The evaluation over a set of systems handling lists and linear integer arithmetic confirms that the transformed systems are drastically more simple to solve than the original ones.

ABSTRACT. We present a tool that transforms nondeterministic omega-automata to semi-deterministic omega-automata. The tool Seminator and accepts transition-based generalized Büchi automata (TGBA) as input and produces automata with two kinds of semi-determinism. The implemented procedure performs degeneralization and semi-determinization simultaneously and employs several other optimizations. We experimentaly evaluate Seminator in the context of LTL to semi-deterministic automata translation.

ABSTRACT. Gossip protocols deal with a group of communicating agents, each holding a private information, and aim at arriving at a situation in which all the agents know each other secrets. Distributed epistemic gossip protocols are particularly simple distributed programs that use as guards formulas from an epistemic logic. Recently, the implementability of these distributed protocols and the problems of their partial correctness and termination were shown to be decidable, but decidability of their fair termination was left open. We show that for any distributed epistemic gossip protocol, its fair (in respect to agents or rules) termination is decidable.

ABSTRACT. The paper looks at tooling aspects of transforming C# programs into symbolic transducers with branching rules (BSTs). The latter are used for describing list comprehensions that incorporate loop-carried state. One concrete application is log analysis where input streams of data are transformed into output streams of data via intermediate pipelines of transducers. The paper presents algorithms for translating C# to BSTs, and for exposing control state in BSTs.