Integer Linear Programming for Sequence Problems: A general approach to reduce the problem size

Sequence problems belong to the most challenging interdisciplinary topics of the actuality. They are ubiquitous in science and daily life and occur, for example, in form of DNA sequences encoding all information of an organism, as a text (natural or formal) or in form of a computer program. Therefore, sequence problems occur in many variations in computational biology (drug development), coding theory, data compression, quantitative and computational linguistics (e.g. machine translation). In recent years appeared some proposals to formulate sequence problems like the closest string problem (CSP) and the farthest string problem (FSP) as an Integer Linear Programming Problem (ILPP). In the present talk we present a general novel approach to reduce the size of the ILPP by grouping isomorphous columns of the string matrix together. The approach is of practical use, since the solution of sequence problems is very time consuming, in particular when the sequences are long.

The architecture of children’s use of language and tools when problem solving collaboratively with robotics

This paper demonstrates, following Vygotsky, that language and tool use has a critical role in the collaborative problem-solving behaviour of school-age children. It reports original ethnographic classroom research examining the convergence of speech and practical activity in children’s collaborative problem solving with robotics programming tasks. The researchers analysed children’s interactions during a series of problem solving experiments in which Lego Mindstorms toolsets were used by teachers to create robotics design challenges among 24 students in a Year 4 Australian classroom (students aged 8.5–9.5 years). The design challenges were incrementally difficult, beginning with basic programming of straight line movement, and progressing to more complex challenges involving programming of the robots to raise Lego figures from conduit pipes using robots as pulleys with string and recycled materials. Data collection involved micro-genetic analysis of students’ speech interactions with tools, peers, and other experts, teacher interviews, and student focus group data. Coding the repeated patterns in the transcripts, the authors outline the structure of the children’s social speech in joint problem solving, demonstrating the patterns of speech and interaction that play an important role in the socialisation of the school-age child’s practical intellect.

Probability Distribution of the Eigenvalues of the Random String Equation

The probability distribution of the eigenvalues of a second-order stochastic boundary value problem is considered. The solution is characterized in terms of the zeros of an associated initial value problem. It is further shown that the probability distribution is related to the solution of a first-order nonlinear stochastic differential equation. Solutions of this equation based on the theory of Markov processes and also on the closure approximation are presented. A string with stochastic mass distribution is considered as an example for numerical work. The theoretical probability distribution functions are compared with digital simulation results. The comparison is found to be reasonably good.

Correlation between corona current and radio interference due to high voltage insulator string

The Radio Interference (RI) from electric power transmission line hardware, if not controlled, poses serious electromagnetic interference to system in the vicinity. The present work mainly concerns with the RI from the insulator string along with the associated line hardware. The laboratory testing for the RI levels are carried out through the measurement of the conducted radio interference levels. However such measurements do not really locate the coronating point, as well as, the mode of corona. At the same time experience shows that it is rather difficult to locate the coronating points by mere inspection. After a thorough look into the intricacies of the problem, it is ascertained that the measurement of associated ground end currents could give a better picture of the prevailing corona modes and their intensities. A study on the same is attempted in the present work. Various intricacies of the problem,features of ground end current pulses and its correlation with RI are dealt with. Owing to the complexity of such experimental investigations, the study made is not fully complete nevertheless it seems to be first of its kind.

Efficient Algorithms for Answering the m-Closest Keywords Query

As an important type of spatial keyword query, the m-closest keywords (mCK) query finds a group of objects such that they cover all query keywords and have the smallest diameter, which is defined as the largest distance between any pair of objects in the group. The query is useful in many applications such as detecting locations of web resources. However, the existing work does not study the intractability of this problem and only provides exact algorithms, which are computationally expensive.

In this paper, we prove that the problem of answering mCK queries is NP-hard. We first devise a greedy algorithm that has an approximation ratio of 2. Then, we observe that an mCK query can be approximately answered by finding the circle with the smallest diameter that encloses a group of objects together covering all query keywords. We prove that the group enclosed in the circle can answer the mCK query with an approximation ratio of 2 over 3. Based on this, we develop an algorithm for finding such a circle exactly, which has a high time complexity. To improve efficiency, we propose another two algorithms that find such a circle approximately, with a ratio of 2 over √3 + ε. Finally, we propose an exact algorithm that utilizes the group found by the 2 over √3 + ε)-approximation algorithm to obtain the optimal group. We conduct extensive experiments using real-life datasets. The experimental results offer insights into both efficiency and accuracy of the proposed approximation algorithms, and the results also demonstrate that our exact algorithm outperforms the best known algorithm by an order of magnitude.

Adaptive tackling of the swinging problem for a 2 DOF crane – payload system

The control of a crane carrying its payload by an elastic string corresponds to a task in which precise, indirect control of a subsystem dynamically coupled to a directly controllable subsystem is needed. This task is interesting since the coupled degree of freedom has little damping and it is apt to keep swinging accordingly. The traditional approaches apply the input shaping technology to assist the human operator responsible for the manipulation task. In the present paper a novel adaptive approach applying fixed point transformations based iterations having local basin of attraction is proposed to simultaneously tackle the problems originating from the imprecise dynamic model available for the system to be controlled and the swinging problem, too. The most important phenomenological properties of this approach are also discussed. The control considers the 4th time-derivative of the trajectory of the payload. The operation of the proposed control is illustrated via simulation results.

An integer linear programming approach for approximate string comparison

We introduce a problem called maximum common characters in blocks (MCCB), which arises in applications of approximate string comparison, particularly in the unification of possibly erroneous textual data coming from different sources. We show that this problem is NP-complete, but can nevertheless be solved satisfactorily using integer linear programming for instances of practical interest. Two integer linear formulations are proposed and compared in terms of their linear relaxations. We also compare the results of the approximate matching with other known measures such as the Levenshtein (edit) distance. (C) 2008 Elsevier B.V. All rights reserved.

Towards a hybrid compactification with a scalar-tensor global cosmic string

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Effect of denture fabrication and wear on closest speaking space and interocclusal distance during deglutition

Statement of problem. The accuracy of assessing maxillomandibular relationships for trial bases and dentures using phonetic and swallowing methods has not been compared to that observed with definitive prostheses. Thus, there is no evidence to prove whether measurements obtained through such methods remain the same after adaptation to dentures.Purpose. This study investigated changes in the closest speaking space, interocclusal rest space, and interocclusal distance during deglutition in edentulous patients during and after complete denture treatment.Material and methods. Eighteen edentulous subjects participated in this study and measurements were performed after 7 Intervals of time: (1) with occlusion rims and record bases following creation of the maxillomandibular relationship record, (2) with trial dentures, (3) at Insertion of definitive complete dentures, (4) 1 week, (5) 2 weeks, (6) 1 month, and (7) 3 months after insertion. Recordings of interocclusal distances were made with a mandibular kinesiograph. Closest speaking space was measured during the pronunciation of the word 'seis'. The distance between postural rest position and centric occlusion, or interocclusal rest space, was measured using a kinesiograph. Interocclusal distance during deglutition was tested by recording the closest mandibular position recorded during swallowing of 20 mL of water. Data were analyzed using repeated-measure ANOVA, followed by the Student-Newman-Keuls test (alpha=.05).Results. A significant (P <.01)reduction in the mean closest speaking space was found when it was evaluated using occlusion rims and record bases (4.6 mm) compared with other stages (3.0 to 3.4 mm). No significant differences were found in mean interocclusal rest space and interocclusal distance during deglutition among the time periods evaluated.Conclusions. The presence of occlusion rims can influence mandibular position during pronunciation of the /s/ sound. The arrangement of artificial teeth changes the closest speaking space. However, rest position and deglutition were not affected, either during denture fabrication or short-term use.

The magnetic field of a current carrying cosmic string

The magnetostatic field of an infinite rectilinear current placed in the stationary gravitational field of a rotating cosmic string is found. An interesting aspect of this problem is that although the metric is mathematically very simple, its physical meaning is not trivial. It depends only on topological parameters. So, the cosmic string vacuum space-time is locally equivalent to the Minkowski space-time, but not globally. The calculations are so simple that they can easily be shown in the classroom. © 1997 American Association of Physics Teachers.

Aspects of Integrability in Gauge/String Correspondence

In this thesis, we present our work about some generalisations of ideas, techniques and physical interpretations typical for integrable models to one of the most outstanding advances in theoretical physics of nowadays: the AdS/CFT correspondences. We have undertaken the problem of testing this conjectured duality under various points of view, but with a clear starting point - the integrability - and with a clear ambitious task in mind: to study the finite-size effects in the energy spectrum of certain string solutions on a side and in the anomalous dimensions of the gauge theory on the other. Of course, the final desire woul be the exact comparison between these two faces of the gauge/string duality. In few words, the original part of this work consists in application of well known integrability technologies, in large parte borrowed by the study of relativistic (1+1)-dimensional integrable quantum field theories, to the highly non-relativisic and much complicated case of the thoeries involved in the recent conjectures of AdS5/CFT4 and AdS4/CFT3 corrspondences. In details, exploiting the spin chain nature of the dilatation operator of N = 4 Super-Yang-Mills theory, we concentrated our attention on one of the most important sector, namely the SL(2) sector - which is also very intersting for the QCD understanding - by formulating a new type of nonlinear integral equation (NLIE) based on a previously guessed asymptotic Bethe Ansatz. The solutions of this Bethe Ansatz are characterised by the length L of the correspondent spin chain and by the number s of its excitations. A NLIE allows one, at least in principle, to make analytical and numerical calculations for arbitrary values of these parameters. The results have been rather exciting. In the important regime of high Lorentz spin, the NLIE clarifies how it reduces to a linear integral equations which governs the subleading order in s, o(s0). This also holds in the regime with L ! 1, L/ ln s finite (long operators case). This region of parameters has been particularly investigated in literature especially because of an intriguing limit into the O(6) sigma model defined on the string side. One of the most powerful methods to keep under control the finite-size spectrum of an integrable relativistic theory is the so called thermodynamic Bethe Ansatz (TBA). We proposed a highly non-trivial generalisation of this technique to the non-relativistic case of AdS5/CFT4 and made the first steps in order to determine its full spectrum - of energies for the AdS side, of anomalous dimensions for the CFT one - at any values of the coupling constant and of the size. At the leading order in the size parameter, the calculation of the finite-size corrections is much simpler and does not necessitate the TBA. It consists in deriving for a nonrelativistc case a method, invented for the first time by L¨uscher to compute the finite-size effects on the mass spectrum of relativisic theories. So, we have formulated a new version of this approach to adapt it to the case of recently found classical string solutions on AdS4 × CP3, inside the new conjecture of an AdS4/CFT3 correspondence. Our results in part confirm the string and algebraic curve calculations, in part are completely new and then could be better understood by the rapidly evolving developments of this extremely exciting research field.

Quantum Integrability in Non-Linear Sigma Models related to Gauge/String Correspondences

The Thermodynamic Bethe Ansatz analysis is carried out for the extended-CP^N class of integrable 2-dimensional Non-Linear Sigma Models related to the low energy limit of the AdS_4xCP^3 type IIA superstring theory. The principal aim of this program is to obtain further non-perturbative consistency check to the S-matrix proposed to describe the scattering processes between the fundamental excitations of the theory by analyzing the structure of the Renormalization Group flow. As a noteworthy byproduct we eventually obtain a novel class of TBA models which fits in the known classification but with several important differences. The TBA framework allows the evaluation of some exact quantities related to the conformal UV limit of the model: effective central charge, conformal dimension of the perturbing operator and field content of the underlying CFT. The knowledge of this physical quantities has led to the possibility of conjecturing a perturbed CFT realization of the integrable models in terms of coset Kac-Moody CFT. The set of numerical tools and programs developed ad hoc to solve the problem at hand is also discussed in some detail with references to the code.

Thermal inflation and the cosmological moduli problem

Ho studiato la possibilità di soluzione per il problema cosmologico dei moduli (CMP) presente a causa della compattificazione delle dimensioni extra tramite un periodo di inflazione a basse energie (Thermal Inflation). L'elaborato consta di cinque capitoli. Il primo introduce il lettore alla problematica dei moduli partendo dalla teoria Kaluza-Klein. Il secondo riguarda interamente il CMP e altri problemi cosmologici associati ai moduli. Nel terzo viene descritta la thermal inflation e le condizioni di funzionamento. Nel quarto capitolo viene preso in esame il problema di stabilizzazione dei moduli nella teoria di stringa tipo IIB: vengono descritti sia il meccanismo KKTL che il LVS. L'ultimo capitolo consiste nel calcolo della diluizione dei moduli, enunciata prima in un contesto generale e infine applicata al LVS, tramite la thermal inflation. Viene altresì presa in esame la possibilità di due epoche di thermal inflation, al fine di ottenere una diluizione più efficiente dei moduli. In LVS sono presenti due moduli, differenti per massa e vita media. Il più leggero è soggetto al CMP e si trova che, anche dopo due periodi di thermal inflation vi è ancora un numero eccessivo di tali campi, in quanto se da un lato la thermal inflation ne diliusca la densità iniziale, dall'altro ne causa una forte riproduzione, dovuta essenzialmente alle caratteristiche del modulo

Moduli stabilisation and soft supersymmetry breaking in string compactifications

In this thesis, we shall work in the framework of type IIB Calabi-Yau flux compactifications and present a detailed review of moduli stabilisation studying in particular the phenomenological implications of the LARGE-volume scenario (LVS). All the physical relevant quantities such as moduli masses and soft-terms, are computed and compared to the phenomenological constraints that today guide the research. The structure of this thesis is the following. The first chapter introduces the reader to the fundamental concepts that are essentially supersymmetry-breaking, supergravity and string moduli, which represent the basic framework of our discussion. In the second chapter we focus our attention on the subject of moduli stabilisation. Starting from the structure of the supergravity scalar potential, we point out the main features of moduli dynamics, we analyse the KKLT and LARGE-volume scenario and we compute moduli masses and couplings to photons which play an important role in the early-universe evolution since they are strictly related to the decay rate of moduli particles. The third chapter is then dedicated to the calculation of soft-terms, which arise dynamically from gravitational interactions when moduli acquire a non-zero vacuum expectation value (VeV). In the last chapter, finally, we summarize and discuss our results, underling their phenomenological aspects. Moreover, in the last section we analyse the implications of the outcomes for standard cosmology, with particular interest in the cosmological moduli problem.