Search

Your search keyword '"Křetínský, Jan"' showing total 409 results
Start Over Author "Křetínský, Jan"

Refine your results

more »

more »

more »

more »
409 results on '"Křetínský, Jan"'

101. Measuring Performance of Continuous-Time Stochastic Processes using Timed Automata

Author

Brázdil, Tomáš, Krčál, Jan, Křetínský, Jan, Kučera, Antonín, and Řehák, Vojtěch

Subjects
Computer Science - Systems and Control, Computer Science - Formal Languages and Automata Theory
Abstract

We propose deterministic timed automata (DTA) as a model-independent language for specifying performance and dependability measures over continuous-time stochastic processes. Technically, these measures are defined as limit frequencies of locations (control states) of a DTA that observes computations of a given stochastic process. Then, we study the properties of DTA measures over semi-Markov processes in greater detail. We show that DTA measures over semi-Markov processes are well-defined with probability one, and there are only finitely many values that can be assumed by these measures with positive probability. We also give an algorithm which approximates these values and the associated probabilities up to an arbitrarily small given precision. Thus, we obtain a general and effective framework for analysing DTA measures over semi-Markov processes.

Published
2011

105. 30 Years of Modal Transition Systems: Survey of Extensions and Analysis

Author

Křetínský, Jan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Aceto, Luca, editor, Bacci, Giorgio, editor, Bacci, Giovanni, editor, Ingólfsdóttir, Anna, editor, Legay, Axel, editor, and Mardare, Radu, editor

Published
2017
Full Text
View/download PDF

106. Faster Statistical Model Checking for Unbounded Temporal Properties

Author

Daca, Przemysław, Henzinger, Thomas A., Křetínský, Jan, Petrov, Tatjana, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Chechik, Marsha, editor, and Raskin, Jean-François, editor

Published
2016
Full Text
View/download PDF

107. Limit-Deterministic Büchi Automata for Linear Temporal Logic

Author

Sickert, Salomon, Esparza, Javier, Jaax, Stefan, Křetínský, Jan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Chaudhuri, Swarat, editor, and Farzan, Azadeh, editor

Published
2016
Full Text
View/download PDF

108. Survey of Statistical Verification of Linear Unbounded Properties: Model Checking and Distances

Author

Křetínský, Jan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Margaria, Tiziana, editor

Published
2016
Full Text
View/download PDF

109. MoChiBA: Probabilistic LTL Model Checking Using Limit-Deterministic Büchi Automata

Author

Sickert, Salomon, Křetínský, Jan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Artho, Cyrille, editor, Legay, Axel, editor, and Peled, Doron, editor

Published
2016
Full Text
View/download PDF

117. The Hanoi Omega-Automata Format

Author

Babiak, Tomáš, Blahoudek, František, Duret-Lutz, Alexandre, Klein, Joachim, Křetínský, Jan, Müller, David, Parker, David, Strejček, Jan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Kroening, Daniel, editor, and Păsăreanu, Corina S., editor

Published
2015
Full Text
View/download PDF

118. Compositionality for Quantitative Specifications

Author

Fahrenberg, Uli, Křetínský, Jan, Legay, Axel, Traonouez, Louis-Marie, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Lanese, Ivan, editor, and Madelaine, Eric, editor

Published
2015
Full Text
View/download PDF

121. Rabinizer 3: Safraless Translation of LTL to Small Deterministic Automata

Author

Komárková, Zuzana, Křetínský, Jan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Cassez, Franck, editor, and Raskin, Jean-François, editor

Published
2014
Full Text
View/download PDF

131. Formalizing and Guaranteeing Human-Robot Interaction: As robots begin to interact closely with humans, we need to build systems worthy of trust regarding the safety and quality of the interaction.

Author

KRESS-GAZIT, HADAS, EDER, KERSTIN, HOFFMAN, GUY, ADMONI, HENNY, ARGALL, BRENNA, EHLERS, RÜDIGER, HECKMAN, CHRISTOFFER, JANSEN, NILS, KNEPPER, ROSS, KŘETÍNSKÝ, JAN, LEVY-TZEDEK, SHELLY, LI, JAMY, MURPHEY, TODD, RIEK, LAUREL, and SADIGH, DORSA

Subjects
HUMAN-robot interaction, TRUST, SOCIAL norms, HUMAN behavior, ALGORITHMS
Abstract

ROBOT CAPABILITIES ARE maturing across domains, from self-driving cars to bipeds to drones. As a result, robots will soon no longer be confined to safetycontrolled industrial settings; instead, they will directly interact with the general public. The growing field of human-robot interaction (HRI) studies various aspects of this scenario, from social norms to collaborative manipulation to human-robot teaming, and more. Researchers in HRI have made great strides in developing models, methods, and algorithms for robots acting with and around humans. [ABSTRACT FROM AUTHOR]

Published
2021
Full Text
View/download PDF

133. Modal Process Rewrite Systems

Author

Beneš, Nikola, Křetínský, Jan, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Roychoudhury, Abhik, editor, and D’Souza, Meenakshi, editor

Published
2012
Full Text
View/download PDF

134. Dual-Priced Modal Transition Systems with Time Durations

Author

Beneš, Nikola, Křetínský, Jan, Guldstrand Larsen, Kim, Møller, Mikael H., Srba, Jiří, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bjørner, Nikolaj, editor, and Voronkov, Andrei, editor

Published
2012
Full Text
View/download PDF

135. Parametric Modal Transition Systems

Author

Beneš, Nikola, Křetínský, Jan, Larsen, Kim G., Møller, Mikael H., Srba, Jiří, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Bultan, Tevfik, editor, and Hsiung, Pao-Ann, editor

Published
2011
Full Text
View/download PDF

136. Modal Transition Systems: Composition and LTL Model Checking

Author

Beneš, Nikola, Černá, Ivana, Křetínský, Jan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Bultan, Tevfik, editor, and Hsiung, Pao-Ann, editor

Published
2011
Full Text
View/download PDF

137. Stochastic Real-Time Games with Qualitative Timed Automata Objectives

Author

Brázdil, Tomáš, Krčál, Jan, Křetínský, Jan, Kučera, Antonín, Řehák, Vojtěch, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Gastin, Paul, editor, and Laroussinie, François, editor

Published
2010
Full Text
View/download PDF

138. Checking Thorough Refinement on Modal Transition Systems Is EXPTIME-Complete

Author

Beneš, Nikola, Křetínský, Jan, Larsen, Kim G., Srba, Jiří, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Leucker, Martin, editor, and Morgan, Carroll, editor

Published
2009
Full Text
View/download PDF

139. Verification of Discrete-Time Markov Decision Processes

Author

Křetínský, Jan (Prof. Dr.), Křetínský, Jan (Prof. Dr.);Baier, Christel (Prof. Dr.), Meggendorfer, Tobias, Křetínský, Jan (Prof. Dr.), Křetínský, Jan (Prof. Dr.);Baier, Christel (Prof. Dr.), and Meggendorfer, Tobias

Abstract

In this thesis, we discuss the verification of discrete-time Markov decision processes (MDP). First, we present two novel algorithms to efficiently compute mean-payoff queries on MDP. Then, we provide efficient practical implementations of LTL-to-automata translation algorithms, which play a central role in probabilistic LTL model checking. We introduce the novel notion of cores in an MDP, which provide a framework to speed up many approximation-based tasks by automatically removing irrelevant states. Finally, we present a significant step towards risk-aware analysis of probabilistic systems., Diese Arbeit beschäftigt sich mit der Verifikation von Markov Entscheidungsprozessen in diskreter Zeit. Wir definieren zwei neue Algorithmen um mean-payoff Probleme effizient zu lösen. Dann geben wir eine Überblick über eine effiziente Implementierung von LTL-zu-Automaten Übersetzungsalgorithmen, welche insbesondere im Kontext der probabilistischen Verifikation von LTL Formeln eine zentrale Rolle spielen. Danach beschreiben wir das neue Konzept eines Kerns, welches uns erlaubt automatisch unwichtige Teile des Systems zu entfernen und dadurch anschließende Analyse zu beschleunigen. Zuletzt präsentieren wir einen wichtigen Schritt in Richtung risikobewusster Analyse von probabilistischen Systemen.

Published
2021

140. A Learning Twist on Controllers: Synthesis via Partial Exploration and Concise Representations

Author

Křetínský, Jan (Prof. Dr.), Křetínský, Jan (Prof. Dr.);Guldstrand Larsen R, Kim (Prof.);Althoff, Matthias (Prof. Dr.), Ashok, Pranav, Křetínský, Jan (Prof. Dr.), Křetínský, Jan (Prof. Dr.);Guldstrand Larsen R, Kim (Prof.);Althoff, Matthias (Prof. Dr.), and Ashok, Pranav

Abstract

Quantitative model checking and controller synthesis deal with the task of automatically synthesizing reliable controllers for safety-critical systems. We address the state-space explosion challenge and present two distinct algorithms based on partial exploration for discrete as well as continuous-time Markov decision processes. Further, we present the first results on representing controllers of probabilistic and hybrid systems concisely and explainably using decision trees., Quantitative Modellüberprüfung und Reglersynthese befassen sich mit der Aufgabe, zuverlässige Regler für sicherheitskritische Systeme automatisch zu synthetisieren. Wir befassen uns mit der Herausforderung der Zustandsraumexplosion und stellen zwei verschiedene Algorithmen vor, die auf der partiellen Erkundung von diskreten bzw. zeitkontinuierlichen Markov-Entscheidungsprozessen basieren. Darüber hinaus präsentieren wir die ersten Ergebnisse zur Darstellung von Reglern probabilistischer und hybrider Systeme knapp und erklärbar mithilfe von Entscheidungsbäumen.

Published
2021

141. A Unified Translation of Linear Temporal Logic to ω-Automata.

Author

ESPARZA, JAVIER, KŘETÍNSKÝ, JAN, and SICKERT, SALOMON

Subjects
TRANSLATIONS, LOGIC
Abstract

We present a unified translation of linear temporal logic (LTL) formulas into deterministic Rabin automata (DRA), limit-deterministic Büchi automata (LDBA), and nondeterministic Büchi automata (NBA). The translations yield automata of asymptotically optimal size (double or single exponential, respectively). All three translations are derived from one single Master Theorem of purely logical nature. The Master Theorem decomposes the language of a formula into a positive Boolean combination of languages that can be translated into ω-automata by elementary means. In particular, Safra's, ranking, and breakpoint constructions used in other translations are not needed. We further give evidence that this theoretical clean and compositional approach does not lead to large automata per se and in fact in the case of DRAs yields significantly smaller automata compared to the previously known approach using determinisation of NBAs. [ABSTRACT FROM AUTHOR]

Published
2020
Full Text
View/download PDF

147. Monte Carlo Tree Search with Advice

Author

Raskin, Jean-François, Filiot, Emmanuel, Geeraerts, Gilles, Křetínský, Jan, Larsen, Kim Guldstrand, Chakraborty, Debraj, Raskin, Jean-François, Filiot, Emmanuel, Geeraerts, Gilles, Křetínský, Jan, Larsen, Kim Guldstrand, and Chakraborty, Debraj

Abstract

We study how to efficiently combine techniques from formal methods and learning for online computation of a strategy that aims at optimizing the expected long-term reward in large systems modelled as Markov decision processes (MDPs). This strategy is computed with a receding horizon and using Monte Carlo tree search (MCTS). MCTS algorithm is augmented with the notion of advice which guides the search in the relevant part of the tree using exact methods. We show that the classical theoretical guarantees of the Monte Carlo tree search are still maintained after this augmentation. To lower the latency of MCTS algorithms with advice, we propose to replace advice coming from exact algorithms with an artificial neural network trained using an expert imitation framework. To demonstrate the practical interest of our techniques, we implement them on different systems modelled as MDPs: in the game of Pac-Man and Frozen Lake and also for safe and optimal scheduling of jobs in a task system., Doctorat en Sciences, info:eu-repo/semantics/nonPublished

Published
2022

148. Anytime Guarantees for Reachability in Uncountable Markov Decision Processes

Author

Kush Grover and Jan Křetínský and Tobias Meggendorfer and Maximilian Weininger, Grover, Kush, Křetínský, Jan, Meggendorfer, Tobias, Weininger, Maximilian, Kush Grover and Jan Křetínský and Tobias Meggendorfer and Maximilian Weininger, Grover, Kush, Křetínský, Jan, Meggendorfer, Tobias, and Weininger, Maximilian

Abstract

We consider the problem of approximating the reachability probabilities in Markov decision processes (MDP) with uncountable (continuous) state and action spaces. While there are algorithms that, for special classes of such MDP, provide a sequence of approximations converging to the true value in the limit, our aim is to obtain an algorithm with guarantees on the precision of the approximation. As this problem is undecidable in general, assumptions on the MDP are necessary. Our main contribution is to identify sufficient assumptions that are as weak as possible, thus approaching the "boundary" of which systems can be correctly and reliably analyzed. To this end, we also argue why each of our assumptions is necessary for algorithms based on processing finitely many observations. We present two solution variants. The first one provides converging lower bounds under weaker assumptions than typical ones from previous works concerned with guarantees. The second one then utilizes stronger assumptions to additionally provide converging upper bounds. Altogether, we obtain an anytime algorithm, i.e. yielding a sequence of approximants with known and iteratively improving precision, converging to the true value in the limit. Besides, due to the generality of our assumptions, our algorithms are very general templates, readily allowing for various heuristics from literature in contrast to, e.g., a specific discretization algorithm. Our theoretical contribution thus paves the way for future practical improvements without sacrificing correctness guarantees.

Published
2022
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results