ITC/USA 2010 Conference Proceedings / The Forty-Sixth Annual International Telemetering Conference and Technical Exhibition / October 25-28, 2010 / Town and Country Resort & Convention Center, San Diego, California / This paper describes a model of how to configure settings on instrumentation. For any given instrument there may be 100s of settings that can be set to various values. However, randomly selecting values for each setting is not likely to produce a valid configuration. By "valid" we mean a set of setting values that can be implemented by each instrument. The valid configurations must satisfy a set of dependency rules between the settings and other constraints. The formalization provided allows for identification of different sets of configurations settings under control by different systems and organizations. Similarly, different rule sets are identified. A primary application of this model is in the context of a multi-vendor system especially when including vendors that maintain proprietary rules governing their systems. This thus leads to a discussion of an application user interface (API) between different systems with different rules and settings.

BACKGROUND:Shewanella is a genus of facultatively anaerobic, Gram-negative bacteria that have highly adaptable metabolism which allows them to thrive in diverse environments. This quality makes them an attractive bacterial target for research in bioremediation and microbial fuel cell applications. Constraint-based modeling is a useful tool for helping researchers gain insights into the metabolic capabilities of these bacteria. However, Shewanella oneidensis MR-1 is the only strain with a genome-scale metabolic model constructed out of 21 sequenced Shewanella strains.RESULTS:In this work, we updated the model for Shewanella oneidensis MR-1 and constructed metabolic models for three other strains, namely Shewanella sp. MR-4, Shewanella sp. W3-18-1, and Shewanella denitrificans OS217 which span the genus based on the number of genes lost in comparison to MR-1. We also constructed a Shewanella core model that contains the genes shared by all 21 sequenced strains and a few non-conserved genes associated with essential reactions. Model comparisons between the five constructed models were done at two levels - for wildtype strains under different growth conditions and for knockout mutants under the same growth condition. In the first level, growth/no-growth phenotypes were predicted by the models on various carbon sources and electron acceptors. Cluster analysis of these results revealed that the MR-1 model is most similar to the W3-18-1 model, followed by the MR-4 and OS217 models when considering predicted growth phenotypes. However, a cluster analysis done based on metabolic gene content revealed that the MR-4 and W3-18-1 models are the most similar, with the MR-1 and OS217 models being more distinct from these latter two strains. As a second level of comparison, we identified differences in reaction and gene content which give rise to different functional predictions of single and double gene knockout mutants using Comparison of Networks by Gene Alignment (CONGA). Here, we showed how CONGA can be used to find biomass, metabolic, and genetic differences between models.CONCLUSIONS:We developed four strain-specific models and a general core model that can be used to do various in silico studies of Shewanella metabolism. The developed models provide a platform for a systematic investigation of Shewanella metabolism to aid researchers using Shewanella in various biotechnology applications.

Constraint Programming is a powerful technique for solving large-scale combinatorial (optimisation) problems. However, it is often inaccessible to users without expert knowledge in the area, precluding the wide-spread use of Constraint Programming techniques. This thesis addresses this issue in three main contributions. First, we propose a simple ‘model-and-solve’ approach, consisting of a framework where the user formulates a solver-independent problem model, which is then automatically tailored to the input format of a selected constraint solver (a process similar to compiling a high-level modelling language to machine code). The solver is then executed on the input, solver, and solutions (if they exist) are returned to the user. This allows the user to formulate constraint models without requiring any particular background knowledge of the respective solver and its solving technique. Furthermore, since the framework can target several solvers, the user can explore different types of solvers. Second, we extend the tailoring process with model optimisations that can compensate for a wide selection of poor modelling choices that novices (and experts) in Constraint Programming often make and hence result in redundancies. The elimination of these redundancies by the proposed optimisation techniques can result in solving time speedups of over an order of magnitude, in both naive and expert models. Furthermore, the optimisations are particularly light-weight, adding negligible overhead to the overall translation process. The third contribution is the implementation of this framework in the tool TAILOR, that currently translates 2 different solver-independent modelling languages to 3 different solver formats and is freely available online. It performs almost all optimisation techniques that are proposed in this thesis and demonstrates its significance in our empirical analysis. In summary, this thesis presents a framework that facilitates modelling for both experts and novices: problems can be formulated in a clear, high-level fashion, without requiring any particular background knowledge about constraint solvers and their solving techniques, while (sometimes naturally occurring) redundancies in the model are eliminated for practically no additional cost, improving the respective model in solving performance by up to an order of magnitude.

No description available.

Declarative, object-oriented configuration management systems are widely used, and there is a desire to extend such systems with automated analysis and decision-making. This thesis introduces a new formulation for configuration management problems based on the tools and techniques of constraint programming, which enables automated decision-making. We present ConfSolve, an object-oriented declarative configuration language, in which logical constraints on a system can be specified. Verification, impact analysis, and the generation of valid configurations can then be performed. This is achieved via translation to the MiniZinc constraint programming language, which is in turn solved via the Gecode constraint solver. We formally define the syntax, type system, and semantics of ConfSolve, in order to provide it with a rigorous foundation. Additionally we show that our implementation outperforms previous work, which utilised an SMT solver, while adding new features such as optimisation. We next develop an extension of the ConfSolve language, which facilitates not only one-off configuration tasks, but also subsequent re-configurations in which the previous state of the system is taken into account. In a practical setting one does not wish for a re-configuration to deviate too far from the existing state, unless the benefits are substantial. Re-configuration is of crucial importance if automated configuration systems are to gain industry adoption. We present a novel approach to incorporating state-change into ConfSolve while remaining declarative and providing acceptable performance.

This study seeks to explore the concept of ἀνάγκη (and the related terms ἀναγκαίος and ἀναγκαίως) in Greek literature written before 400 BCE. All passages containing these words from the time period were located, translated and analysed according to specific criteria concerning the usage and interpretation of the term. The resulting exploration was then split into five main sections: physical compulsion, moral compulsion, cosmology, circumstantial compulsion and the personification of compulsion. These sections were then examined according to both context and subtle differences in the meaning of ἀνάγκη terms within these contexts. The vast majority concerned some form of violence, physical force or fear of violent repercussions. Although the focus was on the interpretation of texts dating to before 400 BCE, owing to their fragmentary nature but considerable importance, the cosmological texts had to be examined in conjunction with later texts in order to shed more light on the meaning of ἀνάγκη in this context. Statistical analysis was performed on the 466 texts located and they were further analysed to track variations across time and genre-specific usages. Several types of usage were seen to develop only towards the end of the fifth century after 450 BCE including the notion of relative compulsions; the necessity for revenge and compelled alliances were seen to develop at this time. Recommendations were made with regards to the best and most appropriate translations; the majority of passages would require either the translation of coercion, constraint or compulsion for ἀνάγκη with the exception of the adjectival ἀναγκαίος which can mean blood relatives or similarly obligated individuals. The translation of necessity, although generally the given interpretation of ἀνάγκη was seldom appropriate since it did not grasp the entire meaning of the term in context.

A wide range of problems can be formalized as a set of constraints that need to be satisfied. In fact, such a model is called a constraint satisfaction problem (CSP). Another way to represent a problem is to express it as a formula in propositional logic, or, in other words, a Boolean satisfiability problem (SAT). In the quest to find efficient algorithms for solving instances of CSP and SAT specialised software has been developed. It is, however, not clear when should we choose a SAT-solver over a constraint solver (and vice versa). CSP-solvers are known for their domain-specific reasoning, whereas SAT-solvers are considered to be remarkably fast on Boolean instances. In this thesis we tackle these issues by investigating the connections between CSP and SAT. In order to answer the question why SAT-solvers are so efficient on certain classes of CSP instances, we first present the various ways one can encode a CSP instance into SAT. Next, we show that with some encodings SAT-solvers simulate the effects of enforcing a form of local consistency, called k-consistency, in expected polynomial-time. Thus SAT-solvers are able to solve CSP instances of bounded-width structure efficiently in contrast to conventional constraint solvers. By considering the various ways one can encode CSP domains into SAT, we give theoretical reasons for choosing a particular SAT encoding for several important classes of CSP instances. In particular, we show that with this encoding many problem instances that can be solved in polynomial-time will still be easily solvable once they are translated into SAT. Furthermore, we show that this is not true for several other encodings. Finally, we compare the various ways one can use a SAT-solver to solve the classical problem of the pigeonhole principle. We perform both theoretical and empirical comparison of the various encodings. We conclude that none of the known encodings for the classical representation of the problem will result in an efficiently-solvable SAT instance. Thus in this case constraint solvers are a much better choice.

Title: Universal Constraint Language Author: Peter Piják Department / Institute: Department of Software Engineering Supervisor of the master thesis: Mgr. Martin Nečaský, Ph.D. Abstract: Today's software applications are typically compound of system of more application components. By modeling of software, various integrity constraint languages are used for particular parts of model (e.g. OCL for UML class diagrams, Schematron for XML or SQL triggers for relational databases). Constraint expressions need to be converted to expressions over different meta-models. These tasks are non-trivial. In this thesis, a new common language Universal Constraint Language (UCL) for expressing integrity constraints over various data meta-models is introduced. It is formally defined and also its parser is implemented. We also present semi-automatic translating between constraints over various meta-models; and deriving constraints from the introduced language to constraints in specific constraint languages. Keywords: constraint language, model-driven architecture, universal formalism

by Hui Kau Cheung Henry. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 107-112). / Abstracts in English and Chinese. / Abstract --- p.ii / Acknowledgments --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Organizations of the Thesis --- p.2 / Chapter 2 --- Background --- p.4 / Chapter 2.1 --- Constraint Satisfaction Problems --- p.4 / Chapter 2.1.1 --- Local Consistency Algorithm --- p.5 / Chapter 2.1.2 --- Backtracking Solver --- p.8 / Chapter 2.1.3 --- The Branch-and-Bound Algorithm --- p.10 / Chapter 2.2 --- Over-constrained Problems --- p.14 / Chapter 2.2.1 --- Weighted Constraint Satisfaction Problems --- p.15 / Chapter 2.2.2 --- Possibilistic Constraint Satisfaction Problems --- p.15 / Chapter 2.2.3 --- Fuzzy Constraint Satisfaction Problems --- p.16 / Chapter 2.2.4 --- Partial Constraint Satisfaction Problems --- p.17 / Chapter 2.2.5 --- Semiring-Based Constraint Satisfaction Problems --- p.18 / Chapter 2.2.6 --- Valued Constraint Satisfaction Problems --- p.22 / Chapter 2.3 --- The Theory of Constraint Hierarchies --- p.23 / Chapter 2.4 --- Related Work --- p.26 / Chapter 2.4.1 --- An Incremental Hierarchical Constraint Solver --- p.28 / Chapter 2.4.2 --- Transforming Constraint Hierarchies into Ordinary Con- straint System --- p.29 / Chapter 2.4.3 --- The SCSP Framework --- p.30 / Chapter 2.4.4 --- The DeltaStar Algorithm --- p.32 / Chapter 2.4.5 --- A Plug-In Architecture of Constraint Hierarchy Solvers --- p.34 / Chapter 3 --- Local Consistency in Constraint Hierarchies --- p.36 / Chapter 3.1 --- A Reformulation of Constraint Hierarchies --- p.37 / Chapter 3.1.1 --- Error Indicators --- p.37 / Chapter 3.1.2 --- A Reformulation of Comparators --- p.38 / Chapter 3.1.3 --- A Reformulation of Solution Set --- p.40 / Chapter 3.2 --- Local Consistency in Classical CSPs --- p.41 / Chapter 3.3 --- Local Consistency in SCSPs --- p.42 / Chapter 3.4 --- Local Consistency in CHs --- p.46 / Chapter 3.4.1 --- The Operations of Error Indicator --- p.47 / Chapter 3.4.2 --- Constraint Hierarchy k-Consistency --- p.49 / Chapter 3.4.3 --- A Comparsion between CHAC and PAC --- p.50 / Chapter 3.4.4 --- The CHAC Algorithm --- p.52 / Chapter 3.4.5 --- Time and Space Complexities of the CHAC Algorithm --- p.53 / Chapter 3.4.6 --- Correctness of the CHAC Algorithm --- p.56 / Chapter 4 --- A Consistency-Based Finite Domain Constraint Hierarchy Solver --- p.59 / Chapter 4.1 --- The Branch-and-Bound CHAC Solver --- p.59 / Chapter 4.2 --- Correctness of the Branch-and-Bound CHAC Solver --- p.61 / Chapter 4.3 --- An Example Execution Trace --- p.64 / Chapter 4.4 --- Experiments and Results --- p.66 / Chapter 4.4.1 --- Experimental Setup --- p.68 / Chapter 4.4.2 --- The First Experiment --- p.71 / Chapter 4.4.3 --- The Second Experiment --- p.94 / Chapter 5 --- Concluding Remarks --- p.103 / Chapter 5.1 --- Summary and Contributions --- p.103 / Chapter 5.2 --- Future Work --- p.104 / Bibliography --- p.107

I hypothesize and find that the variation in corporate tax avoidance is jointly determined by firms’ incentive and opportunities to avoid taxes. Specifically, the positive relation between financial constraints (my proxy for an incentive to avoid taxes) and tax avoidance is significantly stronger for firms with high tax planning opportunities (TPO), where TPO is the distance between a firm’s actual and predicted ETRs. I further show that firms with TPOs based on high permanent (temporary) book-tax differences exhibit more permanent (temporary) book-tax differences under financial constraints. From a risk perspective, I find no evidence that financially constrained firms with low TPO exhibit more tax risk but some evidence that those with high TPO do so. In general, the findings in this paper provide evidence consistent with an incentive-opportunity interaction story to help explain differences in corporate tax avoidance.