Martin Raszyk
Martin Raszyk has a total of 28 co-authors. Here are the top co-authors by number of shared publications:
- Dmitriy Traytel
University of Copenhagen
7 shared publications - Joshua Schneider
ETH Zurich
4 shared publications - Srđan Krstić
ETH Zurich, Zurich, Switzerland
4 shared publications David Basin
3 shared publications- David Basin
Department of Computer Science, ETH Zurich, Zurich, Switzerland
3 shared publications - Elisabet Burjons
RWTH Aachen University
3 shared publications
Latest Publications
- Open Access
- 22 December 2023
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 19, Is (4)
Efficient Evaluation of Arbitrary Relational Calculus Queries
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.
- 22 December 2023
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 19, Is (4)
Open AccessEfficient Evaluation of Arbitrary Relational Calculus Queries
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
- 20 April 2023
- Published by Springer Nature
- p. 473-491
Explainable Online Monitoring of Metric Temporal Logic
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.
- 20 April 2023
- Published by Springer Nature
- p. 473-491
Open AccessExplainable Online Monitoring of Metric Temporal Logic
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.
- Open Access
- 25 July 2022
- Published by Springer Nature in Acta Informatica
- Vol. 59 (4) , 427-450
Reoptimization of parameterized problems
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}$$ . 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}$$ using crown decompositions only, which improves the size of the kernel achievable with this technique in the classic problem.- 25 July 2022
- Published by Springer Nature in Acta Informatica
- Vol. 59 (4) , 427-450
Open AccessReoptimization of parameterized problems
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}$$ . 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}$$ using crown decompositions only, which improves the size of the kernel achievable with this technique in the classic problem. - Open Access
- 30 March 2022
- Published by Springer Nature
- p. 236-253
Verified First-Order Monitoring with Recursive Rules
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.
- 30 March 2022
- Published by Springer Nature
- p. 236-253
Open AccessVerified First-Order Monitoring with Recursive Rules
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
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.
Open AccessFrom Finite-Valued Nondeterministic Transducers to Deterministic Two-Tape Automata
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.
- 24 June 2020
- Published by Springer Nature
- Vol. 12166, 432-453
A Formally Verified, Optimized Monitor for Metric First-Order Dynamic Logic
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.
- 24 June 2020
- Published by Springer Nature
- Vol. 12166, 432-453
A Formally Verified, Optimized Monitor for Metric First-Order Dynamic Logic
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.