52 citations · 113 across the 8 of their papers we have counts for
14 papers
The Reactive Synthesis Competition (SYNTCOMP): 2018-2021
Swen Jacobs, Guillermo A. Perez, Remco Abraham +22
We report on the last four editions of the reactive synthesis competition (SYNTCOMP 2018-2021). We briefly describe the evaluation scheme and the experimental setup of SYNTCOMP. Th…
Equivalence of Linear Tree Transducers with Output in the Free Group
Raphaela Löbel, Michael Luttenberger, Helmut Seidl
We show that equivalence of deterministic linear tree transducers can be decided in polynomial time when their outputs are interpreted over the free group. Due to the cancellation…
On the Balancedness of Tree-to-word Transducers
Raphaela Löbel, Michael Luttenberger, Helmut Seidl
A language over an alphabet of opening () and closing () brackets, is balanced if it is a subset of the Dyck language over , and…
The 5th Reactive Synthesis Competition (SYNTCOMP 2018): Benchmarks, Participants & Results
Swen Jacobs, Roderick Bloem, Maximilien Colange +11
We report on the fifth reactive synthesis competition (SYNTCOMP 2018). We introduce four new benchmark classes that have been added to the SYNTCOMP library, and briefly describe th…
Practical Synthesis of Reactive Systems from LTL Specifications via Parity Games
Michael Luttenberger, Philipp J. Meyer, Salomon Sickert
The synthesis of reactive systems from linear temporal logic (LTL) specifications is an important aspect in the design of reliable software and hardware. We present our adaption of…
Quantitative Implementation Strategies for Safety Controllers
Philipp J. Meyer, Matthias Rungger, Michael Luttenberger +2
We consider the symbolic controller synthesis approach to enforce safety specifications on perturbed, nonlinear control systems. In general, in each state of the system several con…
Computing the longest common prefix of a context-free language in polynomial time
Michael Luttenberger, Raphaela Palenta, Helmut Seidl
We present two structural results concerning longest common prefixes of non-empty languages. First, we show that the longest common prefix of the language generated by a context-fr…
Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity
Georg Bachmeier, Michael Luttenberger, Maximilian Schlund
We answer two open questions by (Gruber, Holzer, Kutrib, 2009) on the state-complexity of representing sub- or superword closures of context-free grammars (CFGs): (1) We prove a (t…
An Extension of Parikh's Theorem beyond Idempotence
Michael Luttenberger, Maximilian Schlund
The commutative ambiguity of a context-free grammar G assigns to each Parikh vector v the number of distinct leftmost derivations yielding a word with Parikh vector v. Based on the…
Parikh's Theorem: A simple and direct automaton construction
Javier Esparza, Pierre Ganty, Stefan Kiefer +1
Parikh's theorem states that the Parikh image of a context-free language is semilinear or, equivalently, that every context-free language has the same Parikh image as some regular…
Space-efficient scheduling of stochastically generated tasks
Tomáš Brázdil, Javier Esparza, Stefan Kiefer +1
We study the problem of scheduling tasks for execution by a processor when the tasks can stochastically generate new tasks. Tasks can be of different types, and each type has a fix…
Computing the Least Fixed Point of Positive Polynomial Systems
Javier Esparza, Stefan Kiefer, Michael Luttenberger
We consider equation systems of the form X_1 = f_1(X_1, ..., X_n), ..., X_n = f_n(X_1, ..., X_n) where f_1, ..., f_n are polynomials with positive real coefficients. In vector form…
Strategy Iteration using Non-Deterministic Strategies for Solving Parity Games
Michael Luttenberger
This article extends the idea of solving parity games by strategy iteration to non-deterministic strategies: In a non-deterministic strategy a player restricts himself to some non-…
Convergence Thresholds of Newton's Method for Monotone Polynomial Equations
Javier Esparza, Stefan Kiefer, Michael Luttenberger
Monotone systems of polynomial equations (MSPEs) are systems of fixed-point equations where each is a polynomial w…