On linear order and computation : The expressiveness of interactive computations on linear orders and computations indexed by ordinals

We solve the Dynamic Ehrenfeucht-Fra\"iss\'e Game on linear orders for both players, yielding a normal form for quantifier-rank equivalence classes of linear orders in first-order logic, infinitary logic, and generalized-infinitary logics with linearly ordered clocks. We show that Scott Sentences can be manipulated quickly, classified into local information, and consistency can be decided effectively in the length of the Scott Sentence. We describe a finite set of linked automata moving continuously on a linear order. Running them on ordinals, we compute the ordinal truth predicate and compute truth in the constructible universe of set-theory. Among the corollaries are a study of semi-models as efficient database of both model-theoretic and formulaic information, and a new proof of the atomicity of the Boolean algebra of sentences consistent with the theory of linear order -- i.e., that the finitely axiomatized theories of linear order are dense.

Locality and order-invariant logics

Malli on logiikassa käytetty abstraktio monille matemaattisille objekteille. Esimerkiksi verkot, ryhmät ja metriset avaruudet ovat malleja. Äärellisten mallien teoria on logiikan osa-alue, jossa tarkastellaan logiikkojen, formaalien kielten, ilmaisuvoimaa malleissa, joiden alkioiden lukumäärä on äärellinen. Rajoittuminen äärellisiin malleihin mahdollistaa tulosten soveltamisen teoreettisessa tietojenkäsittelytieteessä, jonka näkökulmasta logiikan kaavoja voidaan ajatella ohjelmina ja äärellisiä malleja niiden syötteinä. Lokaalisuus tarkoittaa logiikan kyvyttömyyttä erottaa toisistaan malleja, joiden paikalliset piirteet vastaavat toisiaan. Väitöskirjassa tarkastellaan useita lokaalisuuden muotoja ja niiden säilymistä logiikkoja yhdistellessä. Kehitettyjä työkaluja apuna käyttäen osoitetaan, että Gaifman- ja Hanf-lokaalisuudeksi kutsuttujen varianttien välissä on lokaalisuuskäsitteiden hierarkia, jonka eri tasot voidaan erottaa toisistaan kasvavaa dimensiota olevissa hiloissa. Toisaalta osoitetaan, että lokaalisuuskäsitteet eivät eroa toisistaan, kun rajoitutaan tarkastelemaan äärellisiä puita. Järjestysinvariantit logiikat ovat kieliä, joissa on käytössä sisäänrakennettu järjestysrelaatio, mutta sitä on käytettävä siten, etteivät kaavojen ilmaisemat asiat riipu valitusta järjestyksestä. Määritelmää voi motivoida tietojenkäsittelyn näkökulmasta: vaikka ohjelman syötteen tietojen järjestyksellä ei olisi odotetun tuloksen kannalta merkitystä, on syöte tietokoneen muistissa aina jossakin järjestyksessä, jota ohjelma voi laskennassaan hyödyntää. Väitöskirjassa tutkitaan minkälaisia lokaalisuuden muotoja järjestysinvariantit ensimmäisen kertaluvun predikaattilogiikan laajennukset yksipaikkaisilla kvanttoreilla voivat toteuttaa. Tuloksia sovelletaan tarkastelemalla, milloin sisäänrakennettu järjestys lisää logiikan ilmaisuvoimaa äärellisissä puissa.

Fast Linear Algorithm for Active Rules Application in Transition P Systems

Transition P systems are computational models based on basic features of biological membranes and the observation of biochemical processes. In these models, membrane contains objects multisets, which evolve according to given evolution rules. In the field of Transition P systems implementation, it has been detected the necessity to determine whichever time are going to take active evolution rules application in membranes. In addition, to have time estimations of rules application makes possible to take important decisions related to the hardware / software architectures design. In this paper we propose a new evolution rules application algorithm oriented towards the implementation of Transition P systems. The developed algorithm is sequential and, it has a linear order complexity in the number of evolution rules. Moreover, it obtains the smaller execution times, compared with the preceding algorithms. Therefore the algorithm is very appropriate for the implementation of Transition P systems in sequential devices.

The Borel Complexity of Isomorphism for Some First Order Theories

In this work we consider several instances of the following problem: "how complicated can the isomorphism relation for countable models be?"' Using the Borel reducibility framework, we investigate this question with regard to the space of countable models of particular complete first-order theories. We also investigate to what extent this complexity is mirrored in the number of back-and-forth inequivalent models of the theory. We consider this question for two large and related classes of theories. First, we consider o-minimal theories, showing that if T is o-minimal, then the isomorphism relation is either Borel complete or Borel. Further, if it is Borel, we characterize exactly which values can occur, and when they occur. In all cases Borel completeness implies lambda-Borel completeness for all lambda. Second, we consider colored linear orders, which are (complete theories of) a linear order expanded by countably many unary predicates. We discover the same characterization as with o-minimal theories, taking the same values, with the exception that all finite values are possible except two. We characterize exactly when each possibility occurs, which is similar to the o-minimal case. Additionally, we extend Schirrman's theorem, showing that if the language is finite, then T is countably categorical or Borel complete. As before, in all cases Borel completeness implies lambda-Borel completeness for all lambda.

On measurement of top polarization as a probe of t(t)over-bar production mechanisms at the LHC

In this note we demonstrate the use of top polarization in the study of t (t) over bar resonances at the LHC, in the possible case where the dynamics implies a non-zero top polarization. As a probe of top polarization we construct an asymmetry in the decay-lepton azimuthal angle distribution (corresponding to the sign of cos phi(l)) in the laboratory. The asymmetry is non-vanishing even for a symmetric collider like the LHC, where a positive z axis is not uniquely defined. The angular distribution of the leptons has the advantage of being a faithful top-spin analyzer, unaffected by possible anomalous tbW couplings, to linear order. We study, for purposes of demonstration, the case of a Z' as might exist in the little Higgs models. We identify kinematic cuts which ensure that our asymmetry reflects the polarization in sign and magnitude. We investigate possibilities at the LHC with two energy options: root s = 14TeV and root s = 7TeV, as well as at the Tevatron. At the LHC the model predicts net top quark polarization of the order of a few per cent for M-Z' similar or equal to 1200GeV, being as high as 10% for a smaller mass of the Z' of 700GeV and for the largest allowed coupling in the model, the values being higher for the 7TeV option. These polarizations translate to a deviation from the standard-model value of azimuthal asymmetry of up to about 4% (7%) for 14 (7) TeV LHC, whereas for the Tevatron, values as high as 12% are attained. For the 14TeV LHC with an integrated luminosity of 10 fb(-1), these numbers translate into a 3 sigma sensitivity over a large part of the range 500 less than or similar to M-Z' less than or similar to 1500GeV.

Time-dependent transitions with time-space noncommutativity and its implications in quantum optics

We study the time-dependent transitions of a quantum-forced harmonic oscillator in noncommutative R(1,1) perturbatively to linear order in the noncommutativity theta. We show that the Poisson distribution gets modified, and that the vacuum state evolves into a `squeezed' state rather than a coherent state. The time evolutions of uncertainties in position and momentum in vacuum are also studied and imply interesting consequences for modeling nonlinear phenomena in quantum optics.

Rainbow colouring of split and threshold Graphs

A rainbow colouring of a connected graph is a colouring of the edges of the graph, such that every pair of vertices is connected by at least one path in which no two edges are coloured the same. Such a colouring using minimum possible number of colours is called an optimal rainbow colouring, and the minimum number of colours required is called the rainbow connection number of the graph. A Chordal Graph is a graph in which every cycle of length more than 3 has a chord. A Split Graph is a chordal graph whose vertices can be partitioned into a clique and an independent set. A threshold graph is a split graph in which the neighbourhoods of the independent set vertices form a linear order under set inclusion. In this article, we show the following: 1. The problem of deciding whether a graph can be rainbow coloured using 3 colours remains NP-complete even when restricted to the class of split graphs. However, any split graph can be rainbow coloured in linear time using at most one more colour than the optimum. 2. For every integer k ≥ 3, the problem of deciding whether a graph can be rainbow coloured using k colours remains NP-complete even when restricted to the class of chordal graphs. 3. For every positive integer k, threshold graphs with rainbow connection number k can be characterised based on their degree sequence alone. Further, we can optimally rainbow colour a threshold graph in linear time.

New physics in e(+)e(-) -> Z(gamma) at the ILC with polarized beams: explorations beyond conventional anomalous triple gauge boson couplings

One of the most-studied signals for physics beyond the standard model in the production of gauge bosons in electron-positron collisions is due to the anomalous triple gauge boson couplings in the Z(gamma) final state. In this work, we study the implications of this at the ILC with polarized beams for signals that go beyond traditional anomalous triple neutral gauge boson couplings. Here we report a dimension-8 CP-conserving Z(gamma)Z vertex that has not found mention in the literature. We carry out a systematic study of the anomalous couplings in general terms and arrive at a classification. We then obtain linear-order distributions with and without CP violation. Furthermore, we place the study in the context of general BSM interactions represented by e(+)e(-)Z(gamma) contact interactions. We set up a correspondence between the triple gauge boson couplings and the four-point contact interactions. We also present sensitivities on these anomalous couplings, which will be achievable at the ILC with realistic polarization and luminosity.

Integrals of motion for one-dimensional Anderson localized systems

Anderson localization is known to be inevitable in one-dimension for generic disordered models. Since localization leads to Poissonian energy level statistics, we ask if localized systems possess `additional' integrals of motion as well, so as to enhance the analogy with quantum integrable systems. We answer this in the affirmative in the present work. We construct a set of nontrivial integrals of motion for Anderson localized models, in terms of the original creation and annihilation operators. These are found as a power series in the hopping parameter. The recently found Type-1 Hamiltonians, which are known to be quantum integrable in a precise sense, motivate our construction. We note that these models can be viewed as disordered electron models with infinite-range hopping, where a similar series truncates at the linear order. We show that despite the infinite range hopping, all states but one are localized. We also study the conservation laws for the disorder free Aubry-Andre model, where the states are either localized or extended, depending on the strength of a coupling constant. We formulate a specific procedure for averaging over disorder, in order to examine the convergence of the power series. Using this procedure in the Aubry-Andre model, we show that integrals of motion given by our construction are well-defined in localized phase, but not so in the extended phase. Finally, we also obtain the integrals of motion for a model with interactions to lowest order in the interaction.

红毛菜发育过程及其生理基础

红毛菜（Bangia Lyngb.）属于红藻门，与紫菜属同属红毛菜科，其味道和营养都优于紫菜。目前红毛菜栽培产业已在我国福建莆田展开，但栽培技术还有待提高。海藻栽培技术的发展和成熟依赖于对其生长发育过程的认识。本研究针对红毛菜发育过程及相关光合生理展开，并初步探讨了一采自山西娘子关泉淡水红毛菜群体（FWB）的系统地位。 色素突变标记的壳孢子萌发特征表明最初两次分裂产生的4细胞决定了完整植株的形态建成。成熟植株，为雌雄异体。雌性生殖器果胞的标志性分化结构为原始受精丝，环境因子是促发原始受精丝发展的外部因素，其膨大程度随受精的延迟而增大。原孢子是主要的无性生殖孢子类型，在不良环境中，藻体也会形成内生孢子或休眠包囊，或者藻体断裂后重新形成完整的植株。 红毛菜的生长发育很大程度上受环境因子的控制。高温不利于配子体的发育，15-20 ºC比较适宜。红毛菜无性繁殖的最适温度-光照组合为20 ºC-8 h，有性繁殖为15 ºC-12h。 不同发育阶段，PSII实际光合效率（Y(II)）与细胞的健康状况以及光合器官完整性及其在细胞内的分布有关，而与细胞的类型关系不大。健康的假根细胞、已分化未成熟的精子以及果孢子细胞均具有很高的Y(II)。色素体由中间位变为围周位，中央大液泡（营养藻丝）和大小纤维囊泡（成熟孢子与精子）的产生，使得细胞Y(II)降低。刚放散的壳孢子Y(II)很低，说明在壳孢子由贝壳基质释放到自由水体过程，光合作用受到一定程度抑制；而2h后，Y(II)开始恢复，rbcL的转录水平非常高，为孢子的萌发储备物质和能量需求。 在失水和低盐胁迫下，藻体均维持较高的Y(II)。干出处理至藻体重量不再变化，复水后Y(II)可回复初始水平。海生红毛菜在100％淡水培养基中（约20ºC）培养7天后，部分雄性藻体依然活着。从而体现了红毛菜位居高潮带的生理优势。 FWB终生行无性繁殖，藻体形态与发生以及染色体数目（4条）与海生群体没有区别。而rbcL-rbcS Spacer序列显示，红毛菜海生群体（无性和有性）具有完全相同的序列，而FWB与它们有5bp差异，但是与欧洲、北美地区的淡水群体仅1bp不同，初步说明所有淡水红毛菜群体具有共同的原始起源。

Tense, Aspect and the Cognitive Representation of Time

This paper explores the relationships between a computation theory of temporal representation (as developed by James Allen) and a formal linguistic theory of tense (as developed by Norbert Hornstein) and aspect. It aims to provide explicit answers to four fundamental questions: (1) what is the computational justification for the primitive of a linguistic theory; (2) what is the computational explanation of the formal grammatical constraints; (3) what are the processing constraints imposed on the learnability and markedness of these theoretical constructs; and (4) what are the constraints that a linguistic theory imposes on representations. We show that one can effectively exploit the interface between the language faculty and the cognitive faculties by using linguistic constraints to determine restrictions on the cognitive representation and vice versa. Three main results are obtained: (1) We derive an explanation of an observed grammatical constraint on tense?? Linear Order Constraint??m the information monotonicity property of the constraint propagation algorithm of Allen's temporal system: (2) We formulate a principle of markedness for the basic tense structures based on the computational efficiency of the temporal representations; and (3) We show Allen's interval-based temporal system is not arbitrary, but it can be used to explain independently motivated linguistic constraints on tense and aspect interpretations. We also claim that the methodology of research developed in this study??oss-level" investigation of independently motivated formal grammatical theory and computational models??a powerful paradigm with which to attack representational problems in basic cognitive domains, e.g., space, time, causality, etc.

Three-machine shop scheduling with partially ordered processing routes

This paper considers the problem of sequencing n jobs in a three-machine shop with the objective of minimising the maximum completion time. The shop consists of three machines, M1,M2 and M_{3}. A job is first processed on M1 and then is assigned either the route (M2,M_{3}) or the route (M_{3},M2). Thus, for our model the processing route is given by a partial order of machines, as opposed to the linear order of machines for a job shop, or to an arbitrary sequence of machines for an open shop. The main result is on O(nlog n) time heuristic, which generates a schedule with the makespan that is at most 5/3 times the optimum value.

Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvatal, Trotter and the two senior authors proved that for any Delta there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph K(N) with N >= Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Delta. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and O(N(2-1/Delta)log(1/Delta)N) edges, with N = [B`n] for some constant B` that depends only on Delta. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Delta is O(n(2-1/Delta)log(1/Delta)n) Our approach is based on random graphs; in fact, we show that the classical Erdos-Renyi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Delta. The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed. (C) 2011 Elsevier Inc. All rights reserved.

Mapeamento de genes da família das defensinas no genoma do búfalo

Pós-graduação em Zootecnia - FCAV

Incomplete pairwise comparison matrices and weighting methods

A special class of preferences, given by a directed acyclic graph, is considered. They are represented by incomplete pairwise comparison matrices as only partial information is available: for some pairs no comparison is given in the graph. A weighting method satisfies the property linear order preservation if it always results in a ranking such that an alternative directly preferred to another does not have a lower rank. We study whether two procedures, the Eigenvector Method and the Logarithmic Least Squares Method meet this axiom. Both weighting methods break linear order preservation, moreover, the ranking according to the Eigenvector Method depends on the incomplete pairwise comparison representation chosen.