Source author record

Souymodip Chakraborty

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Logic in Computer Science Formal Languages and Automata Theory

Catalog footprint

Research overview

2works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

On the Hardness of PCTL Satisfiability

This paper shows that the satisfiability problem for probabilistic CTL (PCTL, for short) is undecidable. By a reduction from $1\frac{1}{2}$ -player games with PCTL winning objectives, we establish that the PCTL satisfiability problem is $Σ_1^1$ -hard. We present an exponential-time algorithm for the satisfiability of a bounded, negation-closed fragment of PCTL, and show that the satisfiability problem for this fragment is EXPTIME-hard.

preprint2014arXiv

Parametric LTL on Markov Chains

This paper is concerned with the verification of finite Markov chains against parametrized LTL (pLTL) formulas. In pLTL, the until-modality is equipped with a bound that contains variables; e.g., $\Diamond_{\le x}\ φ$ asserts that $φ$ holds within $x$ time steps, where $x$ is a variable on natural numbers. The central problem studied in this paper is to determine the set of parameter valuations $V_{\prec p} (φ)$ for which the probability to satisfy pLTL-formula $φ$ in a Markov chain meets a given threshold $\prec p$ , where $\prec$ is a comparison on reals and $p$ a probability. As for pLTL determining the emptiness of $V_{> 0}(φ)$ is undecidable, we consider several logic fragments. We consider parametric reachability properties, a sub-logic of pLTL restricted to next and $\Diamond_{\le x}$ , parametric Büchi properties and finally, a maximal subclass of pLTL for which emptiness of $V_{> 0}(φ)$ is decidable.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.