tr-announce June 2010

tr-announce@lists.rwth-aachen.de

1 participants
2 discussions

2010-12: Dependency Triples for Improving Termination Analysis of Logic Programs with Cut

by Carsten Fuhs

The following technical report is available from http://aib.informatik.rwth-aachen.de: Dependency Triples for Improving Termination Analysis of Logic Programs with Cut Thomas Ströder, Peter Schneider-Kamp, Jürgen Giesl AIB 2010-12 In very recent work, we introduced a non-termination preserving transformation from logic programs with cut to definite logic programs. While that approach allows us to prove termination of a large class of logic programs with cut automatically, in several cases the transformation results in a non-terminating definite logic program. In this paper we extend the transformation such that logic programs with cut are no longer transformed into definite logic programs, but into dependency triple problems. By the implementation of our new method and extensive experiments, we empirically evaluate the practical benefit of our contributions.

14 years, 3 months

2010-11: Parametric LTL Games

by Carsten Fuhs

The following technical report is available from http://aib.informatik.rwth-aachen.de: Parametric LTL Games Martin Zimmermann AIB 2010-11 We consider graph games of infinite duration with winning conditions in parameterized linear temporal logic, where the temporal operators are equipped with variables for time bounds. In model checking such specifications were introduced as PLTL by Alur et al. and (in a different version called PROMPT-LTL) by Kupferman et al.. Our work lifts their results on model checking for PLTL and PROMPT-LTL to the level of games: we present algorithms that determine whether a player wins a game with respect to some, infinitely many, or all variable valuations. All these algorithms run in doubly-exponential time; so, adding bounded temporal operators does not increase the complexity compared to solving plain LTL games. Furthermore, we show how to determine optimal valuations that allow a player to win a game.

14 years, 3 months

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

tr-announce June 2010