### Book chapter

## Complexity and expressivity of Branching- and Alternating-time temporal logics with finitely many variables

We show that Branching-time temporal logics **CTL** and **CTL***, as well as Alternating-time temporal logics **ATL** and **ATL***, are as semantically expressive in the language with a single propositional variable as they are in the full language, i.e., with an unlimited supply of propositional variables. It follows that satisfiability for **CTL**, as well as for **ATL**, with a single variable is EXPTIME-complete, while satisfiability for **CTL***, as well as for **ATL***, with a single variable is 2EXPTIME-complete,—i.e., for these logics, the satisfiability for formulas with only one variable is as hard as satisfiability for arbitrary formulas.

### In book

It is known that both satisfiability and model-checking problems for propositional Linear-time Temporal Logic, LTL, with only a single propositional variable in the language are PSPACE-complete, which coincides with the complexity of these problems for LTL with an arbitrary number of propositional variables. In the present paper, we show that the same result can be obtained by modifying the original proof of PSPACE-hardness for LTL; i.e., we show how to modify the construction to model the computations of polynomially-space bound Turing machines using only formulas of one variable. We believe that our alternative proof gives additional insight into the semantic and computational properties of LTL.

Modal logics, both propositional and predicate, have been used in computer science since the late 1970s. One of the most important properties of modal logics of relevance to their applications in computer science is the complexity of their satisﬁability problem. The complexity of satisﬁability for modal logics is rather high: it ranges from NP-complete to undecidable for propositional logics and is undecidable for predicate logics. This has, for a long time, motivated research in drawing the borderline between tractable and intractable fragments of propositional modal logics as well as between decidable and undecidable fragments of predicate modal logics. In the present thesis, we investigate some very natural restrictions on the languages of propositional and predicate modal logics and show that placing those restrictions does not decrease complexity of satisﬁability. For propositional languages, we consider restricting the number of propositional variables allowed in the construction of formulas, while for predicate languages, we consider restricting the number of individual variables as well as the number and arity of predicate letters allowed in the construction of formulas. We develop original techniques, which build on and develop the techniques known from the literature, for proving that satisﬁability for a ﬁnite-variable fragment of a propositional modal logic is as computationally hard as satisﬁability for the logic in the full language and adapt those techniques to predicate modal logics and prove undecidability of fragments of such logics in the language with a ﬁnite number of unary predicate letters as well as restrictions on the number of individual variables. The thesis is based on four articles published or accepted for publication. They concern propositional dynamic logics, propositional branchingand alternating-time temporal logics, propositional logics of symmetric rela tions, and ﬁrst-order predicate modal and intuitionistic logics. In all cases, we identify the “minimal,” with regard to the criteria mentioned above, fragments whose satisﬁability is as computationally hard as satisﬁability for the entire logic.

In this paper, we show that the weighted vertex coloring problem can be solved in polynomial on the sum of vertex weights time for {P_5, K_{2,3}, K_{2,3}^+}-free graphs. As a corollary, this fact implies polynomial-time solvability of the unweighted vertex coloring problem for {P_5, K_{2,3}, K_{2,3}^+}-free graphs. As usual, P_5 and K_{2,3} stands, respectively, for the simple path on 5 vertices and for the biclique with the parts of 2 and 3 vertices, K_{2,3} denotes the graph, obtained from a K_{2,3} by joining its degree 3 vertices with an edge.

We investigate the complexity of satisfiability for finite-variable fragments of propositional dynamic logics (PDLs). We consider three formalisms belonging to three representative complexity classes, broadly understood—regular PDL, which is EXPTIME-complete; PDL with intersection, which is 2EXPTIME-complete; and PDL with parallel composition, which is undecidable. We show that, for each of these logics, the complexity of satisfiability remains unchanged even if we only allow as inputs formulas built solely out of propositional constants, i.e. without propositional variables. Moreover, we show that this is a consequence of the richness of the expressive power of variable-free fragments: for all the logics we consider, such fragments are as semantically expressive as entire logics. We conjecture that this is representative of PDL-style, as well as closely related, logics.

Mathematical models of distributed computations, based on the calculus of mobile processes (pi-calculus) are widely used for checking the information security properties of cryptographic protocols. Since pi-calculus is Turing-complete, this problem is undecidable in general case. Therefore, the study is carried out only for some special classes of pi-calculus processes with restricted computational capabilities, for example, for non-recursive processes, in which all runs have a bounded length, for processes with a bounded number of parallel components, etc. However, even in these cases, the proposed checking procedures are time consuming. We assume that this is due to the very nature of the pi -calculus processes. The goal of this paper is to show that even for the weakest model of passive adversary and for relatively simple protocols that use only the basic pi-calculus operations, the task of checking the information security properties of these protocols is co-NP-complete.

This two-volume set (CCIS 905 and CCIS 906) constitutes the refereed proceedings of the Second International Conference on Advances in Computing and Data Sciences, ICACDS 2018, held in Dehradun, India, in April 2018. The 110 full papers were carefully reviewed and selected from 598 submissions. The papers are centered around topics like advanced computing, data sciences, distributed systems organizing principles, development frameworks and environments, software verification and validation, computational complexity and cryptography, machine learning theory, database theory, probabilistic representations.