Construction of the solution of the Chinese Remainder Theorem for polynomials using the method of undetermined coefficients
This article is dedicated to an alternative method of solving of the Chinese Remainder Theorem for polynomials. To construct the solution, a system of linear equations is constructed (using the method of undetermined coefficients) and then solved. The complexity of the proposed method is also calculated.
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.
The asymptotic theory is developed for polynomial sequences that are generated by the three-term higher-order recurrence. Our results generalize known results for p=1, that is, for orthogonal polynomial sequences on the real line that belong to the Blumenthal–Nevai class. As is known, for p≥2, the role of the interval is replaced by a starlike set S of p+1 rays emanating from the origin on which the Q n satisfy a multiple orthogonality condition involving p measures. Here we obtain strong asymptotics for the Q n in the complex plane outside the common support of these measures as well as on the (finite) open rays of their support. In so doing, we obtain an extension of Weyl’s famous theorem dealing with compact perturbations of bounded self-adjoint operators. Furthermore, we derive generalizations of the classical Szegő functions, and we show that there is an underlying Nikishin system hierarchy for the orthogonality measures that is related to the Weyl functions. Our results also have application to Hermite–Padé approximants as well as to vector continued fractions.
We introduce a unital associative algebra associated with degenerate CP1. We show that is a commutative algebra and whose Poincare' series is given by the number of partitions. Thereby, we can regard as a smooth degeneration limit of the elliptic algebra introduced by Feigin and Odesskii [Int. Math. Res. Notices 11, 531 (1997)]. Then we study the commutative family of the Macdonald difference operators acting on the space of symmetric functions. A canonical basis is proposed for this family by using and the Heisenberg representation of the commutative family studied by Shiraishi [ Commun. Math. Phys. 263, 439 (2006)]. It is found that the Ding-Iohara algebra [Lett. Math. Phys. 41, 183 (1997)] provides us with an algebraic framework for the free field construction. An elliptic deformation of our construction is discussed, showing connections with the Drinfeld quasi-Hopf twisting [Leningrad Math. J. 1, 1419 (1990)] in the sence of Babelon-Bernard-Billey [Phys. Lett. B. 375, 89 (1996)], the Ruijsenaars difference operator [Commun. Math. Phys. 110, 191 (1987)], and the operator M(q,t1,t2) of Okounkov-Pandharipande [e-print arXiv:math-ph/0411210].
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.
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.
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.