Büchi, Elgot and Trakhtenbrot provided a seminal connection between monadic second-order logic and finite automata for both finite and infinite words. This BET- Theorem has been extended by Lautemann, Schwentick and Thérien to context-free languages by introducing a monadic second-order logic with an additional existentially quantified second-order variable. This new variable models the stack of pushdown au- tomata. A fundamental study by Cohen and Gold extended the context-free languages to infinite words. Our first main result is a second-order logic in the sense of Lautemann, Schwentick and Thérien with the same expressive power as ω-context-free languages. For our argument, we investigate Greibach normal forms of ω-context-free grammars as well as a new type of Büchi pushdown automata, the simple pushdown automata. Simple pushdown automata do not use e-transitions and can change the stack only by at most one symbol. We show that simple pushdown automata of infinite words suffice to accept all ω-context-free languages. This enables us to use Büchi-type results recently developed for infinite nested words. In weighted automata theory, many classical results on formal languages have been extended into a quantitative setting. Weighted context-free languages of finite words trace back already to Chomsky and Schützenberger. Their work has been extended to infinite words by Ésik and Kuich. As in the theory of formal grammars, these weighted ω-context-free languages, or ω-algebraic series, can be represented as solutions of mixed ω-algebraic systems of equations and by weighted ω-pushdown automata. In our second main result, we show that (mixed) ω-algebraic systems can be trans- formed into Greibach normal form. We then investigate simple pushdown automata in the weighted setting. Here, we give our third main result. We prove that weighted simple pushdown automata of finite words recognize all weighted context-free languages, i.e., generate all algebraic series. Then, we show that weighted simple ω-pushdown automata generate all ω-algebraic series. This latter result uses the former result together with the Greibach normal form that we developed for ω-algebraic systems. As a fourth main result, we prove that for weighted simple ω-pushdown automata, Büchi-acceptance and Muller-acceptance are expressively equivalent. In our fifth main result, we derive a Nivat-like theorem for weighted simple ω- pushdown automata. This theorem states that the behaviors of our automata are precisely the projections of very simple ω-series restricted to ω-context-free languages. The last result, our sixth main result, is a weighted logic with the same expressive power as weighted simple ω-pushdown automata. To prove the equivalence, we use a similar result for weighted nested ω-word automata and apply our present result of expressive equivalence of Muller and Büchi acceptance.

No description available.

No description available.

Three-dimensional gravity-capillary steady waves on water of finite-depth, which are uniformly translating in a horizontal propagation direction and periodic in a transverse direction, are considered. The exact Euler equations are formulated as a spatial dynamic system in which the variable used for the propagating direction is the time-like variable. The existence of the solutions of the system is determined by two non-dimensional constants: the Bond number b and λ (the inverse of the square of the Froude number). The property of Sobolev spaces and the spectral analysis show that the spectrum of the linear part consists of isolated eigenvalues of finite algebraic multiplicity and the number of purely imaginary eigenvalues are finite. The distribution of eigenvalues is described by b and λ. Assume that C₁ is the curve in (b,λ)-plane on which the first two eigenvalues for three-dimensional waves collide at the imaginary axis, and that the intersection point of the curve C₁ with the line λ=1 is (b₀,1) where b₀>0. Two cases (b₀,1) and (b,λ) â C₁ where 0< b< b₀ are investigated. A center-manifold reduction technique and a normal form analysis are applied to show that for each case the dynamical system can be reduced to a system of ordinary differential equations with finite dimensions. The dominant system for the case (b₀,1) is coupled Schrödinger-KdV equations while it is a Schrödinger equation for another case (b,λ) â C₁. Then, from the existence of the homoclinic orbit connecting to the two-dimensional periodic solution (called generalized solitary wave) for the dominant system, it is obtained that such generalized solitary wave solution persists for the original system by using the perturbation method and adjusting some appropriate constants. / Ph. D.

<p>In 1998 the Swedish mathematician Warwick Tucker used rigorous interval arithmetic and normal form theory to prove the existence of a strange attractor in the Lorenz system. In large parts, that proof consists of computations implemented and performed on a computer. This thesis is an independent numerical verification of the result obtained by Warwick Tucker, as well as a study of a higher-dimensional system of ordinary differential equations introduced by the Swedish physicist Lennart Stenflo.</p><p>The same type of mapping data as Warwick Tucker obtained is calculated here via a combination of numerical integration, solving optimisation problems and a coordinate change that brings the system to a normal form around the stationary point in the origin. This data is collected in a graph and the problem of determining the existence of a strange attractor is translated to a few graph theoretical problems. The end result, after the numerical study, is a support for the conclusion that the attractor set of the Lorenz system is a strange attractor and also for the conclusion that the Lorenz-Stenflo system possesses a strange attractor.</p>

Neste trabalho, apresentamos um método algébrico para obter formas normais de campos vetoriais reversíveis equivariantes. Adaptamos o método clássico de Belitskii-Elphick, usando ferramentas da teoria invariante para estabelecer fórmulas que consideram as simetrias e antissimetrias como ponto de partida. Mostramos que este método, mesmo sem simetrias, possui uma estreita relação com o método da transversal completa da teoria de singularidades. Com as ferramentas desenvolvidas nesta tese, a forma normal obtida e uma série formal que não depende do cálculo do kernel do chamado operador homológico. Formas normais para duas classes de campos, ressonantes e não ressonantes, são apresentadas, para diferentes representações do grupo \'Z IND. 2\' x \'Z IND. 2\' cuja linearização tem uma parte nilpotente de dimensão 2 e uma parte semi-simples com autovalores puramente imaginários / We give an algebraic method to obtain normal forms of reversible equivariant vector fields. We adapt the classical method by Belitskii-Elphick using tools from invariant theory to establish formulae that take symmetries into account as a starting point. We show that this method, even without symmetries, has a close relation to complete transversal of singularities theory. Applying the method developed in this thesis, the resulting normal form is a formal series which does not depend of the computation of the kernel of the so called homologic operator. Normal forms of two classes of non-resonant and resonant cases are presented, for dierent representations of the group \'Z INT. 2\' x \'Z INT. 2\' - with linearization having a 2 - dimensional nilpotent part and a semisimple part with purely imaginary eigenvalues

Neste trabalho, apresentamos um método algébrico para obter formas normais de campos vetoriais reversíveis equivariantes. Adaptamos o método clássico de Belitskii-Elphick, usando ferramentas da teoria invariante para estabelecer fórmulas que consideram as simetrias e antissimetrias como ponto de partida. Mostramos que este método, mesmo sem simetrias, possui uma estreita relação com o método da transversal completa da teoria de singularidades. Com as ferramentas desenvolvidas nesta tese, a forma normal obtida e uma série formal que não depende do cálculo do kernel do chamado operador homológico. Formas normais para duas classes de campos, ressonantes e não ressonantes, são apresentadas, para diferentes representações do grupo \'Z IND. 2\' x \'Z IND. 2\' cuja linearização tem uma parte nilpotente de dimensão 2 e uma parte semi-simples com autovalores puramente imaginários / We give an algebraic method to obtain normal forms of reversible equivariant vector fields. We adapt the classical method by Belitskii-Elphick using tools from invariant theory to establish formulae that take symmetries into account as a starting point. We show that this method, even without symmetries, has a close relation to complete transversal of singularities theory. Applying the method developed in this thesis, the resulting normal form is a formal series which does not depend of the computation of the kernel of the so called homologic operator. Normal forms of two classes of non-resonant and resonant cases are presented, for dierent representations of the group \'Z INT. 2\' x \'Z INT. 2\' - with linearization having a 2 - dimensional nilpotent part and a semisimple part with purely imaginary eigenvalues

A common approach in designing relational databases is to start with a relation schema, which is then decomposed into multiple subschemas. A good choice of sub- schemas can often be determined using integrity constraints defined on the schema. Two central questions arise in this context. The first issue is what decompositions should be called "good", i.e., what normal form should be used. The second issue is how to find a decomposition into the desired form. These question have been the subject of intensive research since relational databases came to life. A large number of normal forms have been proposed, and methods for their computation given. However, some of the most popular proposals still have problems: - algorithms for finding decompositions are inefficient - dependency preserving decompositions do not always exist - decompositions need not be optimal w.r.t. redundancy/space/update anomalies We will address these issues in this work by: - designing effcient algorithms for finding dependency preserving decompositions - proposing a new normal form which minimizes overall storage space. This new normal form is then characterized syntactically, and shown to extend existing normal forms.

In 1998 the Swedish mathematician Warwick Tucker used rigorous interval arithmetic and normal form theory to prove the existence of a strange attractor in the Lorenz system. In large parts, that proof consists of computations implemented and performed on a computer. This thesis is an independent numerical verification of the result obtained by Warwick Tucker, as well as a study of a higher-dimensional system of ordinary differential equations introduced by the Swedish physicist Lennart Stenflo. The same type of mapping data as Warwick Tucker obtained is calculated here via a combination of numerical integration, solving optimisation problems and a coordinate change that brings the system to a normal form around the stationary point in the origin. This data is collected in a graph and the problem of determining the existence of a strange attractor is translated to a few graph theoretical problems. The end result, after the numerical study, is a support for the conclusion that the attractor set of the Lorenz system is a strange attractor and also for the conclusion that the Lorenz-Stenflo system possesses a strange attractor. / QC 20101007

Traditional data management technologies originating from business domain are currently facing many challenges from other domains such as scientific research. Data structures in databases are becoming more and more complex and data query functions are moving from the back-end database level towards the front-end user-interface level. Traditional query languages such as SQL, OQL, and form-based query interfaces cannot fully meet the needs today. This research is motivated by the data management issues in life science applications. I propose a methodology for domain-specific conceptual data modeling and querying. The methodology can be applied to any domain to capture more domain semantics and empower end-users to formulate a query at the conceptual level with terminologies and functions familiar to them. The query system resulting from the methodology is designed to work on all major types of database management systems (DBMS) and support end-users to dynamically define and add new domain-specific functions. That is, all user-defined functions can be either pre-defined by domain experts and/or data model creators at the time of system creation, or dynamically defined by end-users from the client side at any time. The methodology has a domain-specific conceptual data model (DSC-DM) and a domain-specific conceptual query language (DSC-QL). DSC-QL uses only the abstract concepts, relationships, and functions defined in DSC-DM. It is a user-oriented high level query language and intentionally designed to be flexible, extensible, and readily usable. DSC-QL queries are much simpler than corresponding SQL or OQL queries because of advanced features such as user-defined functions, composite and set attributes, dot-path expressions, and super-classes. DSC-QL can be translated into SQL and OQL through a dynamic mapping function, and automatically updated when the underlying database schema evolves. The operational and declarative semantics of DSC-QL are formally defined in terms of graphs. A normal form for DSC-QL as a standard format for the mappings from flexible conceptual expressions to restricted SQL or OQL statements is also defined. Two translation algorithms from normalized DSC-QL to SQL and OQL are introduced. Through comparison, DSC-QL is shown to have very good balance between simplicity and expressive power and is suitable for end-users. Implementation details of the query system are reported as well. Two prototypes have been built. One prototype is for neuroscience domain, which is built on an object-oriented DBMS. The other one is for traditional business domain, which is built on a relational DBMS.