Author name cluster

Marcus Gelderie

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

LOPSTR Conference 2024 Conference Paper

Impact and Performance of Randomized Test-Generation Using Prolog

Marcus Gelderie
Maximilian Luff
Maximilian Peltzer

Abstract We study randomized generation of sequences of test-inputs to a system using Prolog. Prolog is a natural fit to generate test-sequences that have complex logical inter-dependent structure. To counter the problems posed by a large (or infinite) set of possible tests, randomization is a natural choice. We study the impact that randomization in conjunction with SLD resolution have on the test performance. To this end, this paper proposes two strategies to add randomization to a test-generating program. One strategy works on top of standard Prolog semantics, whereas the other alters the SLD selection function. We analyze the mean time to reach a test-case, and the mean number of generated test-cases in the framework of Markov chains. Finally, we provide an additional empirical evaluation and comparison between both approaches.

Details

I&C Journal 2017 Journal Article

Classifying recognizable infinitary trace languages using word automata

Namit Chaturvedi
Marcus Gelderie

We address the problem of providing a Borel-like classification of languages of infinite Mazurkiewicz traces, and provide a solution in the framework of ω-automata over infinite words – which is invoked via the sets of linearizations of infinitary trace languages. We identify trace languages whose linearizations are recognized by deterministic weak or deterministic Büchi (word) automata. We present a characterization of the class of linearizations of all recognizable ω-trace languages in terms of Muller (word) automata. Finally, we show that the linearization of any recognizable ω-trace language can be expressed as a Boolean combination of languages recognized by our class of deterministic Büchi automata.

Details DOI

Highlights Conference 2013 Conference Abstract

Strategy composition in compositional games

Marcus Gelderie

When studying games played on finite arenas, the arena is given explicitly, hiding the underlying structure of the arena. We study games where the global arena is a product of several smaller, constituent arenas. We investigate how these "global games" can be solved by playing "component games" on the constituent arenas. To this end, we introduce two kinds of products of arenas. Moreover, we define a suitable notion of strategy composition and show how, for the first notion of product, winning strategies in reachability games can be composed from winning strategies in games on the constituent arenas. For the second kind of product, the complexity of solving the global game shows that a general composition theorem is equivalent to proving Pspace = Exptime. 16: 48 17: 12 Coffee Break

PDF Details

MFCS Conference 2012 Conference Paper

Strategy Machines and Their Complexity

Marcus Gelderie

Abstract We introduce a machine model for the execution of strategies in (regular) infinite games that refines the standard model of Mealy automata. This model of controllers is formalized in the terminological framework of Turing machines. We show how polynomially sized controllers can be found for Muller and Streett games. We are able to distinguish aspects of executing strategies (“size”, “latency”, “space consumption”) that are not visible in Mealy automata. Also, lower bound results are obtained.

Details