MRMartin Raszyk

Martin Raszyk

*This is an algorithmically generated author record based on publicly available information.

Martin Raszyk has a total of 28 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Efficient Evaluation of Arbitrary Relational Calculus Queries

    by Martin Raszyk, David Basin, Srđan Krstić, Dmitriy Traytel

    The relational calculus (RC) is a concise, declarative query language. However, existing RC query evaluation approaches are inefficient and often deviate from established algorithms based on finite tables used in database management systems. We devise a new translation of an arbitrary RC query into two safe-range queries, for which the finiteness of the query's evaluation result is guaranteed. Assuming an infinite domain, the two queries have the following meaning: The first is closed and characterizes the original query's relative safety, i.e., whether given a fixed database, the original query evaluates to a finite relation. The second safe-range query is equivalent to the original query, if the latter is relatively safe. We compose our translation with other, more standard ones to ultimately obtain two SQL queries. This allows us to use standard database management systems to evaluate arbitrary RC queries. We show that our translation improves the time complexity over existing approaches, which we also empirically confirm in both realistic and synthetic experiments.


  • Open Access

    Explainable Online Monitoring of Metric Temporal Logic

    by Leonardo Lima, Andrei Herasimau, Martin Raszyk, Dmitriy Traytel, Simon Yuan

    Runtime monitors analyze system execution traces for policy compliance. Monitors for propositional specification languages, such as metric temporal logic (MTL), produce Boolean verdicts denoting whether the policy is satisfied or violated at a given point in the trace. Given a sufficiently complex policy, it can be difficult for the monitor’s user to understand how the monitor arrived at its verdict. We develop an MTL monitor that outputs verdicts capturing why the policy was satisfied or violated. Our verdicts are proof trees in a sound and complete proof system that we design. We demonstrate that such verdicts can serve as explanations for end users by augmenting our monitor with a graphical interface for the interactive exploration of proof trees. As a second application, our verdicts serve as certificates in a formally verified checker we develop using the Isabelle proof assistant.


  • Monitoring the Internet Computer

    by David Basin, Daniel Stefan Dietiker, Srđan Krstić, Yvonne-Anne Pignolet, Martin Raszyk, Joshua Schneider, Arshavir Ter-Gabrielyan


  • VeriMon: A Formally Verified Monitoring Tool

    by David Basin, Thibault Dardinier, Nico Hauser, Lukas Heimes, Jonathan Julián Huerta Y Munive, Nicolas Kaletsch, Srđan Krstić, Emanuele Marsicano, Martin Raszyk, Joshua Schneider, et al.


  • Open Access

    Reoptimization of parameterized problems

    by Hans-Joachim Böckenhauer, Elisabet Burjons, Martin Raszyk, Peter Rossmanith

    Parameterized complexity allows us to analyze the time complexity of problems with respect to a natural parameter depending on the problem. Reoptimization looks for solutions or approximations for problem instances when given solutions to neighboring instances. We combine both techniques, in order to better classify the complexity of problems in the parameterized setting. Specifically, we see that some problems in the class of compositional problems, which do not have polynomial kernels under standard complexity-theoretic assumptions, do have polynomial kernels under the reoptimization model for some local modifications. We also observe that, for some other local modifications, these same problems do not have polynomial kernels unless $$\mathbf{NP}\subseteq \mathbf{coNP/poly}$$ NP ⊆ coNP / poly . We find examples of compositional problems, whose reoptimization versions do not have polynomial kernels under any of the considered local modifications. Finally, in another negative result, we prove that the reoptimization version of Connected Vertex Cover does not have a polynomial kernel unless Set Cover has a polynomial compression. In a different direction, looking at problems with polynomial kernels, we find that the reoptimization version of Vertex Cover has a polynomial kernel of size $$\varvec{2k+1}$$ 2 k + 1 using crown decompositions only, which improves the size of the kernel achievable with this technique in the classic problem.


  • Open Access

    Verified First-Order Monitoring with Recursive Rules

    by Sheila Zingg, Srđan Krstić, Martin Raszyk, Joshua Schneider, Dmitriy Traytel

    First-order temporal logics and rule-based formalisms are two popular families of specification languages for monitoring. Each family has its advantages and only few monitoring tools support their combination. We extend metric first-order temporal logic (MFOTL) with a recursive let construct, which enables interleaving rules with temporal logic formulas. We also extend VeriMon, an MFOTL monitor whose correctness has been formally verified using the Isabelle proof assistant, to support the new construct. The extended correctness proof covers the interaction of the new construct with the existing verified algorithm, which is subtle due to the presence of the bounded future temporal operators. We demonstrate the recursive let’s usefulness on several example specifications and evaluate our verified algorithm’s performance against the DejaVu monitoring tool.


  • Open Access

    From Finite-Valued Nondeterministic Transducers to Deterministic Two-Tape Automata

    by Elisabet Burjons, Fabian Frei, Martin Raszyk

    The question whether P equals NP revolves around the discrepancy between active production and mere verification by Turing machines. In this paper, we examine the analogous problem for finite transducers and automata. Every nondeterministic finite transducer defines a binary relation associating each input word with all output words that the transducer can successfully produce on the given input. Finite-valued transducers are those for which there is a finite upper bound on the number of output words that the relation associates with every input word. We characterize finite-valued, functional, and unambiguous nondeterministic transducers whose relations can be verified by a deterministic two-tape automaton, show how to construct such an automaton if one exists, and prove the undecidability of the criterion.

  • Multi-head Monitoring of Metric Dynamic Logic

    by Martin Raszyk, David Basin, Dmitriy Traytel


  • A Formally Verified, Optimized Monitor for Metric First-Order Dynamic Logic

    by David Basin, Thibault Dardinier, Lukas Heimes, Srđan Krstić, Martin Raszyk, Joshua Schneider, Dmitriy Traytel

    Runtime monitors for rich specification languages are sophisticated algorithms, especially when they are heavily optimized. To gain trust in them and safely explore the space of possible optimizations, it is important to verify the monitors themselves. We describe the development and correctness proof in Isabelle/HOL of a monitor for metric first-order dynamic logic. This monitor significantly extends previous work on formally verified monitors by supporting aggregations, regular expressions (the dynamic part), and optimizations including multi-way joins adopted from databases and a new sliding window algorithm.


  • Multi-head Monitoring of Metric Temporal Logic

    by Martin Raszyk, David Basin, Srđan Krstić, Dmitriy Traytel