784 research outputs found
Out of order quantifier elimination for Standard Quantified Linear Programs
No full textAbstractIn this paper, we present an out of order quantifier elimination algorithm for a class of Quantified Linear Programs (QLPs) called Standard Quantified Linear Programs (SQLPs). QLPs in general and SQLPs in particular are extremely useful constraint logic programming structures that find wide applicability in the modeling of real-time schedulability specifications; see Subramani [Subramani, K., 2005a. A comprehensive framework for specifying clairvoyance, constraints and periodicity in real-time scheduling. The Computer Journal 48 (3), 259–272]. Consequently any algorithmic advance in their solution has a strong practical impact. Prior to this work, the only known approaches to the solution of QLPs involved sequential variable elimination; see Subramani [Subramani, K., 2003b. An analysis of quantified linear programs. In: Calude, C.S. et al. (Eds.), Proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science. DMTCS. In: Lecture Notes in Computer Science, vol. 2731. Springer-Verlag, pp. 265–277]. In the sequential approach, the innermost quantified variable is eliminated first, followed by the variable which then becomes the innermost quantified variable and so on, until we are left with a single variable from which the satisfiability of the original formula is easily deduced. This approach is applicable in both discrete and continuous domains; however, it is to be noted that the logic demanding the sequential approach requires that the variables are discrete-valued. To the best of our knowledge, the necessity for sequential elimination over continuous-valued variables has not been investigated in the literature. The techniques used in the development of our elimination algorithm may find applications in domains such as classical logic and finite model theory. The final aspect of our research concerns the structure-preserving nature of the algorithm that we introduce here; in general, it is not known whether discrete domains admit such elimination procedures
On the complexity of quantified linear systems
No full textIn this paper, we explore the computational complexity of the
conjunctive fragment of the first-order theory of linear
arithmetic. Quantified propositional formulas of linear
inequalities with quantifier alternations are log-space
complete in or depending on the initial
quantifier. We show that when we restrict ourselves to quantified
conjunctions of linear inequalities, i.e., quantified linear
systems, the complexity classes collapse to polynomial time. In
other words, the presence of universal quantifiers does not alter
the complexity of the linear programming problem, which is known
to be in P. Our result reinforces the importance of
sentence formats from the perspective of computational complexity
Improved algorithms for optimal length resolution refutation in difference constraint systems
No full textAbstract
This paper is concerned with the design and analysis of improved algorithms for determining the optimal length resolution refutation (OLRR) of a system of difference constraints over an integral domain. The problem of finding short explanations for unsatisfiable Difference Constraint Systems (DCS) finds applications in a number of design domains including program verification, proof theory, real-time scheduling, and operations research. These explanations have also been called “certificates” and “refutations” in the literature. This problem was first studied in Subramani (J Autom Reason 43(2):121–137,
2009
), wherein the first polynomial time algorithm was proposed. In this paper, we propose two new strongly polynomial algorithms which improve on the existing time bound. Our first algorithm, which we call the edge progression approach, runs in
O
(
n
2
·
k
+
m
·
n
·
k
) time, while our second algorithm, which we call the edge relaxation approach, runs in
O
(
m
·
n
·
k
) time, where
m
is the number of constraints in the DCS,
n
is the number of program variables, and
k
denotes the length of the shortest refutation. We conducted an extensive empirical analysis of the three OLRR algorithms discussed in this paper. Our experiments indicate that in the case of sparse graphs, the new algorithms discussed in this paper are superior to the algorithm in Subramani (J Autom Reason 43(2):121–137,
2009
). Likewise, in the case of dense graphs, the approach in Subramani (J Autom Reason 43(2):121–137,
2009
) is superior to the algorithms described in this paper. One surprising observation is the superiority of the edge relaxation algorithm over the edge progression algorithm in all cases, although both algorithms have the same asymptotic time complexity.
</jats:p
New Results on Cutting Plane Proofs for Horn Constraint Systems
No full textIn this paper, we investigate properties of cutting plane based refutations for a class of integer programs called Horn constraint systems (HCS). Briefly, a system of linear inequalities A * x >= b is called a Horn constraint system, if each entry in A belongs to the set {0,1,-1} and furthermore there is at most one positive entry per row. Our focus is on deriving refutations i.e., proofs of unsatisfiability of such programs using cutting planes as a proof system. We also look at several properties of these refutations. Horn constraint systems can be considered as a more general form of propositional Horn formulas, i.e., CNF formulas with at most one positive literal per clause. Cutting plane calculus (CP) is a well-known calculus for deciding the unsatisfiability of propositional CNF formulas and integer programs. Usually, CP consists of a pair of inference rules. These are called the addition rule (ADD) and the division rule (DIV). In this paper, we show that cutting plane calculus is still complete for Horn constraints when every intermediate constraint is required to be Horn. We also investigate the lengths of cutting plane proofs for Horn constraint systems
Saliva as an emerging biofluid for clinical diagnosis and applications of MEMS/NEMS in salivary diagnostics
No full textSaliva as a biological fluid is gaining wider acceptance for diagnosing diseases. The growing interest in saliva as a biological fluid is due to its noninvasiveness, ease of use, cost-effectiveness, and multiple sample collection possibilities as well as minimal risk to health care professionals of contracting infectious organisms such as HIV and Hep B. However, the clinical translation of saliva is hampered by our lack of understanding of the biomolecular transportation from blood into saliva, the diurnal variations of biomolecules present in saliva, and relatively low levels of analytes (100th to a 1000th fold less than in blood). We provide information on the current status of salivary research, salivary diagnostics empowered by nanotechnology, and future prospects in this emerging field of saliva diagnostics.\ud
\u
Computational complexity of inclusion queries over polyhedral sets
No full textIn this paper we discuss the computational complexities
of procedures for inclusion queries over polyhedral sets.
The polyhedral sets that we consider occur in a wide
range of applications, ranging from logistics to program
verification. The goal of our study is to establish boundaries
between hard and easy problems in this context
A complexity perspective on entailment of parameterized linear constraints
No full textExtending linear constraints by admitting parameters allows for more abstract problem modeling and reasoning. A lot of focus has been given to conducting research that demonstrates the usefulness of parameterized linear constraints and implementing tools that utilize their modeling strength. However, there is no approach that considers basic theoretical tools related to such constraints that allow for reasoning over them. Hence, in this paper we introduce satisfiability with respect to polyhedral sets and entailment for the class of parameterized linear constraints. In order to study the computational complexities of these problems, we relate them to classes of quantified linear implications. The problem of satisfiability with respect to polyhedral sets is then shown to be co- NP hard. The entailment problem is also shown to be co- NP hard in its general form. Nevertheless, we characterize some subclasses for which this problem is in P. Furthermore, we examine a weakening and a strengthening extension of the entailment problem. The weak entailment problem is proved to be NP complete. On the other hand, the strong entailment problem is shown to be co- NP hard
The importomer—A peroxisomal membrane complex involved in protein translocation into the peroxisome matrix
No full textAbstractThe import of proteins into the peroxisome matrix is an essential step in peroxisome biogenesis, which is critical for normal functioning of most eukaryotic cells. The translocation of proteins across the peroxisome membrane and the dynamic behavior of the import receptors during the import cycle is facilitated by several peroxisome–membrane-associated protein complexes, one of which is called the importomer complex [B. Agne, N.M. Meindl, K. Niederhoff, H. Einwachter, P. Rehling, A. Sickmann, H.E. Meyer, W. Girzalsky, W.H. Kunau, Pex8p: an intraperoxisomal organizer of the peroxisomal import machinery, Mol. Cell 11 (2003) 635–646; P.P. Hazra, I. Suriapranata, W.B. Snyder, S. Subramani, Peroxisome remnants in pex3Δ cells and the requirement of Pex3p for interactions between the peroxisomal docking and translocation subcomplexes, Traffic 3 (2002) 560–574. [1,2]]. We provide below a brief historical perspective regarding the importomer and its role in peroxisome biogenesis. We also identify areas in which further work is needed to uncover the physiological role of the importomer
sj-docx-1-pie-10.1177_09544089221115481 - Supplemental material for Development of protective coating for X8CrNiMoVNb16-13 alloy in high-temperature molten salt environment through high-velocity oxy-fuel sprayed NiCrMoNb and Cr<sub>3</sub>C<sub>2</sub>-25NiCr powder coating
No full textSupplemental material, sj-docx-1-pie-10.1177_09544089221115481 for Development of protective coating for X8CrNiMoVNb16-13 alloy in high-temperature molten salt environment through high-velocity oxy-fuel sprayed NiCrMoNb and Cr3C2-25NiCr powder coating by V Sreenivasulu, P Subramani, V Jayakumar, K Mageshkumar, N Arivazhagan, M Manikandan, Szymon Tofil and M Sathishkumar in Proceedings of the Institution of Mechanical Engineers, Part E: Journal of Process Mechanical Engineering</p
sj-docx-2-pie-10.1177_09544089221115481 - Supplemental material for Development of protective coating for X8CrNiMoVNb16-13 alloy in high-temperature molten salt environment through high-velocity oxy-fuel sprayed NiCrMoNb and Cr<sub>3</sub>C<sub>2</sub>-25NiCr powder coating
No full textSupplemental material, sj-docx-2-pie-10.1177_09544089221115481 for Development of protective coating for X8CrNiMoVNb16-13 alloy in high-temperature molten salt environment through high-velocity oxy-fuel sprayed NiCrMoNb and Cr3C2-25NiCr powder coating by V Sreenivasulu, P Subramani, V Jayakumar, K Mageshkumar, N Arivazhagan, M Manikandan, Szymon Tofil and M Sathishkumar in Proceedings of the Institution of Mechanical Engineers, Part E: Journal of Process Mechanical Engineering</p
- …
