7,010 Works

Software Business, Platforms, and Ecosystems: Fundamentals of Software Production Research (Dagstuhl Seminar 18182)

Pekka Abrahamsson, Jan Bosch, Sjaak Brinkkemper & Alexander Mädche
This report documents the program and the outcomes of Dagstuhl Seminar 18182 "Software Business, Platforms, and Ecosystems: Fundamentals of Software Production Research".

Towards Accountable Systems (Dagstuhl Seminar 18181)

David Eyers, Christopher Millard, Margo Seltzer & Jatinder Singh
This report documents the program and the outcomes of Dagstuhl Seminar 18181 "Towards Accountable Systems", which took place from April 29th to May 4th, 2018, at Schloss Dagstuhl - Leibniz Center for Informatics. Researchers and practitioners from academia and industry were brought together covering broad fields from computer and information science, public policy and law. Many risks and opportunities were discussed that relate to the alignment of systems technologies with developing legal and regulatory requirements...

Algebraic Effect Handlers go Mainstream (Dagstuhl Seminar 18172)

Sivaramakrishnan Krishnamoorthy Chandrasekaran, Daan Leijen, Matija Pretnar & Tom Schrijvers
Languages like C\#, C++, or JavaScript support complex control flow statements like exception handling, iterators (yield), and even asynchrony (async/await) through special extensions. For exceptions, the runtime needs to be extended with exception handling stack frames. For iterators and asynchrony, the situation is more involved, as the compiler needs to turn regular code into stack restoring state machines. Furthermore, these features need to interact as expected, e.g. finally blocks must not be forgotten in the...

Normative Multi-Agent Systems (Dagstuhl Seminar 18171)

Mehdi Dastani, Jürgen Dix, Harkp Verhagen & Serena Villata
This report documents the program and the outcomes of Dagstuhl Seminar 18171 "Normative Multi-Agent Systems". Normative multi-agent systems combine models for multi-agent systems with normative concepts, like obligations, permissions, and prohibitions. As such, they promise to be a suitable model, for example for (regulated) multiagent societies, organizations, electronic institutions, autonomous agent cooperation (with humans-in-the-loop) and much more. The aim of this seminar was to bring together researchers from various scientific disciplines, such as computer science,...

Computational Complexity of a Core Fragment of Halpern-Shoham Logic

Przemyslaw Andrzej Walega
Halpern-Shoham logic (HS) is a highly expressive interval temporal logic but the satisfiability problem of its formulas is undecidable. The main goal in the research area is to introduce fragments of the logic which are of low computational complexity and of expressive power high enough for practical applications. Recently introduced syntactical restrictions imposed on formulas and semantical constraints put on models gave rise to tractable HS fragments for which prototypical real-world applications have already been...

Population Based Methods for Optimising Infinite Behaviours of Timed Automata

Lewis Tolonen, Tim French & Mark Reynolds
Timed automata are powerful models for the analysis of real time systems. The optimal infinite scheduling problem for double-priced timed automata is concerned with finding infinite runs of a system whose long term cost to reward ratio is minimal. Due to the state-space explosion occurring when discretising a timed automaton, exact computation of the optimal infinite ratio is infeasible. This paper describes the implementation and evaluation of ant colony optimisation for approximating the optimal schedule...

An Empirical Study on Bidirectional Recurrent Neural Networks for Human Motion Recognition

Pattreeya Tanisaro & Gunther Heidemann
The deep recurrent neural networks (RNNs) and their associated gated neurons, such as Long Short-Term Memory (LSTM) have demonstrated a continued and growing success rates with researches in various sequential data processing applications, especially when applied to speech recognition and language modeling. Despite this, amongst current researches, there are limited studies on the deep RNNs architectures and their effects being applied to other application domains. In this paper, we evaluated the different strategies available to...

A Stream Reasoning System for Maritime Monitoring

Georgios M. Santipantakis, Akrivi Vlachou, Christos Doulkeridis, Alexander Artikis, Ioannis Kontopoulos & George A. Vouros
We present a stream reasoning system for monitoring vessel activity in large geographical areas. The system ingests a compressed vessel position stream, and performs online spatio-temporal link discovery to calculate proximity relations between vessels, and topological relations between vessel and static areas. Capitalizing on the discovered relations, a complex activity recognition engine, based on the Event Calculus, performs continuous pattern matching to detect various types of dangerous, suspicious and potentially illegal vessel activity. We evaluate...

Learning Qualitative Constraint Networks

Malek Mouhoub, Hamad Al Marri & Eisa Alanazi
Temporal and spatial reasoning is a fundamental task in artificial intelligence and its related areas including scheduling, planning and Geographic Information Systems (GIS). In these applications, we often deal with incomplete and qualitative information. In this regard, the symbolic representation of time and space using Qualitative Constraint Networks (QCNs) is therefore substantial. We propose a new algorithm for learning a QCN from a non expert. The learning process includes different cases where querying the user...

GSM+T: A Timed Artifact-Centric Process Model

Julius Köpke, Johann Eder & Jianwen Su
We introduce an extension to the declarative and artifact-centric Guard Stage Milestone (GSM) process modeling language to represent temporal aspects (duration, deadlines, lower- and upper-bound constraints), define the correctness of executions of GSM processes with respect to temporal constraints, check controllability of processes, compute execution plans respecting temporal constraints, and provide a translation method allowing to execute controllable GSM+T processes on standard GSM Engines.

A Temporal Logic for Modelling Activities of Daily Living

Malte S. Kließ, Catholijn M. Jonker & M. Birna Van Riemsdijk
Behaviour support technology is aimed at assisting people in organizing their Activities of Daily Living (ADLs). Numerous frameworks have been developed for activity recognition and for generating specific types of support actions, such as reminders. The main goal of our research is to develop a generic formal framework for representing and reasoning about ADLs and their temporal relations. This framework should facilitate modelling and reasoning about 1) durative activities, 2) relations between higher-level activities and...

On the Expressive Power of Hybrid Branching-Time Logics

Daniel Kernberger & Martin Lange
Hybrid branching-time logics are a powerful extension of branching-time logics like CTL, CTL^* or even the modal mu-calculus through the addition of binders, jumps and variable tests. Their expressiveness is not restricted by bisimulation-invariance anymore. Hence, they do not retain the tree model property, and the finite model property is equally lost. Their satisfiability problems are typically undecidable, their model checking problems (on finite models) are decidable with complexities ranging from polynomial to non-elementary time....

Reducing epsilon-DC Checking for Conditional Simple Temporal Networks to DC Checking

Luke Hunsberger & Roberto Posenato
Recent work on Conditional Simple Temporal Networks (CSTNs) has introduced the problem of checking the dynamic consistency (DC) property for the case where the reaction time of an execution strategy to observations is bounded below by some fixed epsilon > 0, the so-called epsilon-DC-checking problem. This paper proves that the epsilon-DC-checking problem for CSTNs can be reduced to the standard DC-checking problem for CSTNs - without incurring any computational cost. Given any CSTN S with...

Sound-and-Complete Algorithms for Checking the Dynamic Controllability of Conditional Simple Temporal Networks with Uncertainty

Luke Hunsberger & Roberto Posenato
A Conditional Simple Temporal Network with Uncertainty (CSTNU) is a data structure for representing and reasoning about time. CSTNUs incorporate observation time-points from Conditional Simple Temporal Networks (CSTNs) and contingent links from Simple Temporal Networks with Uncertainty (STNUs). A CSTNU is dynamically controllable (DC) if there exists a strategy for executing its time-points that guarantees the satisfaction of all relevant constraints no matter how the uncertainty associated with its observation time-points and contingent links is...

A Game-Theoretic Approach to Timeline-Based Planning with Uncertainty

Nicola Gigante, Angelo Montanari, Marta Cialdea Mayer, Andrea Orlandini & Mark Reynolds
In timeline-based planning, domains are described as sets of independent, but interacting, components, whose behaviour over time (the set of timelines) is governed by a set of temporal constraints. A distinguishing feature of timeline-based planning systems is the ability to integrate planning with execution by synthesising control strategies for flexible plans. However, flexible plans can only represent temporal uncertainty, while more complex forms of nondeterminism are needed to deal with a wider range of realistic...

Deciding the Consistency of Branching Time Interval Networks

Marco Gavanelli, Alessandro Passantino & Guido Sciavicco
Allen's Interval Algebra (IA) is one of the most prominent formalisms in the area of qualitative temporal reasoning; however, its applications are naturally restricted to linear flows of time. When dealing with nonlinear time, Allen's algebra can be extended in several ways, and, as suggested by Ragni and Wölfl [M. Ragni and S. Wölfl, 2004], a possible solution consists in defining the Branching Algebra (BA) as a set of 19 basic relations (13 basic linear...

Algebraic Operators for Processing Sets of Temporal Intervals in Relational Databases

Andreas Dohr, Christiane Engels & Andreas Behrend
The efficient management of temporal data has become increasingly important for many database applications. Most commercial systems already allow the management of temporal data but the operational support for processing this data is still rather limited. One particular reason is that many extension proposals typically require considerable modifications of the underlying database engine. In this paper, we propose a lightweight solution where temporal operators are realized using a library of user-defined functions. This way the...

On Restricted Disjunctive Temporal Problems: Faster Algorithms and Tractability Frontier

Carlo Comin & Romeo Rizzi
In 2005 T.K.S. Kumar studied the Restricted Disjunctive Temporal Problem (RDTP), a restricted but very expressive class of Disjunctive Temporal Problems (DTPs). An RDTP comes with a finite set of temporal variables, and a finite set of temporal constraints each of which can be either one of the following three types: (t_1) two-variable linear-difference simple constraint; (t_2) single-variable disjunction of many interval constraints; (t_3) two-variable disjunction of two interval constraints only. Kumar showed that RDTPs...

Extending Conditional Simple Temporal Networks with Partially Shrinkable Uncertainty

Carlo Combi & Roberto Posenato
The proper handling of temporal constraints is crucial in many domains. As a particular challenge, temporal constraints must be also handled when different specific situations happen (conditional constraints) and when some event occurrences can be only observed at run time (contingent constraints). In this paper we introduce Conditional Simple Temporal Networks with Partially Shrinkable Uncertainty (CSTNPSUs), in which contingent constraints are made more flexible (guarded constraints) and they are also specified as conditional constraints. It...

Faster Dynamic Controllability Checking for Simple Temporal Networks with Uncertainty

Massimo Cairo, Luke Hunsberger & Romeo Rizzi
Simple Temporal Networks (STNs) are a well-studied model for representing and reasoning about time. An STN comprises a set of real-valued variables called time-points, together with a set of binary constraints, each of the form Y <= X+w. The problem of finding a feasible schedule (i.e., an assignment of real numbers to time-points such that all of the constraints are satisfied) is equivalent to the Single Source Shortest Path problem (SSSP) in the STN graph....

Extracting Interval Temporal Logic Rules: A First Approach

Davide Bresolin, Enrico Cominato, Simone Gnani, Emilio Muñoz-Velasco & Guido Sciavicco
Discovering association rules is a classical data mining task with a wide range of applications that include the medical, the financial, and the planning domains, among others. Modern rule extraction algorithms focus on static rules, typically expressed in the language of Horn propositional logic, as opposed to temporal ones, which have received less attention in the literature. Since in many application domains temporal information is stored in form of intervals, extracting interval-based temporal rules seems...

Results on Alternating-Time Temporal Logics with Linear Past

Laura Bozzelli, Aniello Murano & Loredana Sorrentino
We investigate the succinctness gap between two known equally-expressive and different linear-past extensions of standard CTL^* (resp., ATL^*). We establish by formal non-trivial arguments that the "memoryful" linear-past extension (the history leading to the current state is taken into account) can be exponentially more succinct than the standard "local" linear-past extension (the history leading to the current state is forgotten). As a second contribution, we consider the ATL-like fragment, denoted ATL_{lp}, of the known "memoryful"...

Extending Fairness Expressibility of ECTL+: A Tree-Style One-Pass Tableau Approach

Alexander Bolotov, Montserrat Hermo & Paqui Lucio
Temporal logic has become essential for various areas in computer science, most notably for the specification and verification of hardware and software systems. For the specification purposes rich temporal languages are required that, in particular, can express fairness constraints. For linear-time logics which deal with fairness in the linear-time setting, one-pass and two-pass tableau methods have been developed. In the repository of the CTL-type branching-time setting, the well-known logics ECTL and ECTL^+ were developed to...

Predicting the Evolution of Communities with Online Inductive Logic Programming

George Athanasopoulos, George Paliouras, Dimitrios Vogiatzis, Grigorios Tzortzis & Nikos Katzouris
In the recent years research on dynamic social network has increased, which is also due to the availability of data sets from streaming media. Modeling a network's dynamic behaviour can be performed at the level of communities, which represent their mesoscale structure. Communities arise as a result of user to user interaction. In the current work we aim to predict the evolution of communities, i.e. to predict their future form. While this problem has been...

Model Checking Strategic Ability - Why, What, and Especially: How? (Invited Paper)

Wojciech Jamroga
Automated verification of discrete-state systems has been a hot topic in computer science for over 35 years. Model checking of temporal and strategic properties is one of the most prominent and most successful approaches here. In this talk, I present a brief introduction to the topic, and mention some relevant properties that one might like to verify this way. Then, I describe some recent results on approximate model checking and model reductions, which can be...

Resource Types

  • Text
  • Software

Publication Year

  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006

Registration Year

  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009