Automates à contraintes semilinéaires = Automata with a semilinear constraint

Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la logique, l'algèbre et aux applications. Cette étude est présentée au travers de quatre articles de recherche. Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess des automates de Parikh et en définit des généralisations et restrictions. L'automate de Parikh est un point de départ de cette thèse; nous montrons que ce modèle de calcul est équivalent à l'automate contraint que nous définissons comme un automate qui n'accepte un mot que si le nombre de fois que chaque transition est empruntée répond à une contrainte arithmétique. Ce modèle est naturellement étendu à l'automate de Parikh affine qui effectue une opération affine sur un ensemble de registres lors du franchissement d'une transition. Nous étudions aussi l'automate de Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de fois que chaque lettre y apparaît répond à une contrainte arithmétique. Le deuxième article, Bounded Parikh Automata, étudie les langages bornés des automates de Parikh. Un langage est borné s'il existe des mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont importants dans des domaines applicatifs et présentent usuellement de bonnes propriétés théoriques. Nous montrons que dans le contexte des langages bornés, le déterminisme n'influence pas l'expressivité des automates de Parikh. Le troisième article, Unambiguous Constrained Automata, introduit les automates contraints non ambigus, c'est-à-dire pour lesquels il n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de meilleures propriétés de clôture que l'automate contraint déterministe. Le problème de déterminer si le langage d'un automate contraint non ambigu est régulier est montré décidable. Le quatrième article, Algebra and Complexity Meet Contrained Automata, présente une étude des représentations algébriques qu'admettent les automates contraints et les automates de Parikh affines. Nous déduisons de ces caractérisations des résultats d'expressivité et de complexité. Nous montrons aussi que certaines hypothèses classiques en complexité computationelle sont reliées à des résultats de séparation et de non clôture dans les automates de Parikh affines. La thèse est conclue par une ouverture à un possible approfondissement, au travers d'un certain nombre de problèmes ouverts.

Systems of Parallel Communicating Restarting Automata

In der vorliegenden Dissertation werden Systeme von parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (engl.: systems of parallel communicating restarting automata; abgekürzt PCRA-Systeme) vorgestellt und untersucht. Dabei werden zwei bekannte Konzepte aus den Bereichen Formale Sprachen und Automatentheorie miteinander vescrknüpft: das Modell der Restart-Automaten und die sogenannten PC-Systeme (systems of parallel communicating components). Ein PCRA-System besteht aus endlich vielen Restart-Automaten, welche einerseits parallel und unabhängig voneinander lokale Berechnungen durchführen und andererseits miteinander kommunizieren dürfen. Die Kommunikation erfolgt dabei durch ein festgelegtes Kommunikationsprotokoll, das mithilfe von speziellen Kommunikationszuständen realisiert wird. Ein wesentliches Merkmal hinsichtlich der Kommunikationsstruktur in Systemen von miteinander kooperierenden Komponenten ist, ob die Kommunikation zentralisiert oder nichtzentralisiert erfolgt. Während in einer nichtzentralisierten Kommunikationsstruktur jede Komponente mit jeder anderen Komponente kommunizieren darf, findet jegliche Kommunikation innerhalb einer zentralisierten Kommunikationsstruktur ausschließlich mit einer ausgewählten Master-Komponente statt. Eines der wichtigsten Resultate dieser Arbeit zeigt, dass zentralisierte Systeme und nichtzentralisierte Systeme die gleiche Berechnungsstärke besitzen (das ist im Allgemeinen bei PC-Systemen nicht so). Darüber hinaus bewirkt auch die Verwendung von Multicast- oder Broadcast-Kommunikationsansätzen neben Punkt-zu-Punkt-Kommunikationen keine Erhöhung der Berechnungsstärke. Desweiteren wird die Ausdrucksstärke von PCRA-Systemen untersucht und mit der von PC-Systemen von endlichen Automaten und mit der von Mehrkopfautomaten verglichen. PC-Systeme von endlichen Automaten besitzen bekanntermaßen die gleiche Ausdrucksstärke wie Einwegmehrkopfautomaten und bilden eine untere Schranke für die Ausdrucksstärke von PCRA-Systemen mit Einwegkomponenten. Tatsächlich sind PCRA-Systeme auch dann stärker als PC-Systeme von endlichen Automaten, wenn die Komponenten für sich genommen die gleiche Ausdrucksstärke besitzen, also die regulären Sprachen charakterisieren. Für PCRA-Systeme mit Zweiwegekomponenten werden als untere Schranke die Sprachklassen der Zweiwegemehrkopfautomaten im deterministischen und im nichtdeterministischen Fall gezeigt, welche wiederum den bekannten Komplexitätsklassen L (deterministisch logarithmischer Platz) und NL (nichtdeterministisch logarithmischer Platz) entsprechen. Als obere Schranke wird die Klasse der kontextsensitiven Sprachen gezeigt. Außerdem werden Erweiterungen von Restart-Automaten betrachtet (nonforgetting-Eigenschaft, shrinking-Eigenschaft), welche bei einzelnen Komponenten eine Erhöhung der Berechnungsstärke bewirken, in Systemen jedoch deren Stärke nicht erhöhen. Die von PCRA-Systemen charakterisierten Sprachklassen sind unter diversen Sprachoperationen abgeschlossen und einige Sprachklassen sind sogar abstrakte Sprachfamilien (sogenannte AFL's). Abschließend werden für PCRA-Systeme spezifische Probleme auf ihre Entscheidbarkeit hin untersucht. Es wird gezeigt, dass Leerheit, Universalität, Inklusion, Gleichheit und Endlichkeit bereits für Systeme mit zwei Restart-Automaten des schwächsten Typs nicht semientscheidbar sind. Für das Wortproblem wird gezeigt, dass es im deterministischen Fall in quadratischer Zeit und im nichtdeterministischen Fall in exponentieller Zeit entscheidbar ist.

Numbers and Languages

The thesis presents results obtained during the authors PhD-studies. First systems of language equations of a simple form consisting of just two equations are proved to be computationally universal. These are systems over unary alphabet, that are seen as systems of equations over natural numbers. The systems contain only an equation X+A=B and an equation X+X+C=X+X+D, where A, B, C and D are eventually periodic constants. It is proved that for every recursive set S there exists natural numbers p and d, and eventually periodic sets A, B, C and D such that a number n is in S if and only if np+d is in the unique solution of the abovementioned system of two equations, so all recursive sets can be represented in an encoded form. It is also proved that all recursive sets cannot be represented as they are, so the encoding is really needed. Furthermore, it is proved that the family of languages generated by Boolean grammars is closed under injective gsm-mappings and inverse gsm-mappings. The arguments apply also for the families of unambiguous Boolean languages, conjunctive languages and unambiguous languages. Finally, characterizations for morphisims preserving subfamilies of context-free languages are presented. It is shown that the families of deterministic and LL context-free languages are closed under codes if and only if they are of bounded deciphering delay. These families are also closed under non-codes, if they map every letter into a submonoid generated by a single word. The family of unambiguous context-free languages is closed under all codes and under the same non-codes as the families of deterministic and LL context-free languages.

Bounded seas

Abstract Imprecise manipulation of source code (semi-parsing) is useful for tasks such as robust parsing, error recovery, lexical analysis, and rapid development of parsers for data extraction. An island grammar precisely defines only a subset of a language syntax (islands), while the rest of the syntax (water) is defined imprecisely. Usually water is defined as the negation of islands. Albeit simple, such a definition of water is naive and impedes composition of islands. When developing an island grammar, sooner or later a language engineer has to create water tailored to each individual island. Such an approach is fragile, because water can change with any change of a grammar. It is time-consuming, because water is defined manually by an engineer and not automatically. Finally, an island surrounded by water cannot be reused because water has to be defined for every grammar individually. In this paper we propose a new technique of island parsing —- bounded seas. Bounded seas are composable, robust, reusable and easy to use because island-specific water is created automatically. Our work focuses on applications of island parsing to data extraction from source code. We have integrated bounded seas into a parser combinator framework as a demonstration of their composability and reusability.

Modified silicas covalently bounded to 5,10,15,20-tetrakis(2-hydroxy-5-nitrophenyl)porphyrinato iron(III): synthesis, spectroscopic and EPR characterization. Catalytic studies

In this work we have studied cyclooctene epoxidation with PhIO, using a new iron porphyrin, 5,10,15,20-tetrakis(2-hydroxy-5-nitrophenyl)porphyrinato iron(III), supported on silica matrices via eletrostatic interaction and / or covalent bonds as catalyst. These catalysts were obtained and immobilized on the solid supports propyltrimethylammonium silica (SiN+); propyltrimethylammonium and propylimidazole silica [SiN+(IPG)] and chloropropylsilica (CPS) via elestrostatic interactions and covalent binding. Characterization of the supported catalysts by UV-Vis spectroscopy and EPR (Electron paramagnetic resonance) indicated the presence of a mixture of FeII and FeIII species in all of the three obtained catalysts. In the case of (Z)-cyclooctene epoxidation by PhIO the yields observed for cis-epoxycyclooctane were satisfactory for the reactions catalyzed by the three materials (ranging from 68% to 85%). Such results indicate that immobilization of metalloporphyrins onto solid supports via groups localized on the ortho positions of their mesophenyl rings can lead to efficient catalysts for epoxidation reactions. The catalyst 1-CPS is less active than 1-SiN and 1-SiN(IPG), this argues in favour of the immobilization of this metalloporphyrin onto solids via electrostatic interactions, which is easier to achieve and results in more active oxidation catalysts. Interestingly, the activity of the supported catalysts remained the same even after three successive recyclings; therefore, they are stable under the oxidizing conditions.

ASSOCIATION OF A MYOSIN MOTOR WITH MEMBRANE-BOUNDED PIGMENT GRANULES IN FRESHWATER SHRIMP CHROMATOPHORES: EVIDENCE FROM THE NITELLA ACTIN-CABLE ASSAY

We have adapted an actin-mosin motility assay to examine the interactions in vitro between actin cables isolated from the giant internodal cells of the freshwater alga, Nitella, and pigment granules extracted from red ovarian chromatophores of the freshwater palaemonid shrimp, Macrobrachium olfersi. The chromatophore pigment mass consists of large (0.5-1.0-mu m diameter) membrane-bounded granules, and small (140-nm diameter), a membranous granules, both structurally continuous with the abundant smooth endoplasmic reticulum. Our previous immunocytochemical studies show a myosin motor to be stably associated with the pigment mass; however, to which granule type or membrane the myosin motor is attached is unclear. Here, we show that sodium vanadate, a myosin ATPase inhibitor, markedly increases the affinity of isolated, large, membrane-bounded granules for Nitella actin cables to which they become permanently attached. This interaction does not occur in granule preparations containing ATP with uninhibited, active myosin without vanadate. We propose that a stable state of elevated affinity is established between the granule-located myosin motor and the Nitella actin cables, resulting from a vanadate-inhibited acto-myosin-ADP complex. This finding provides further evidence for a myosin motor positioned on the surface of the membrane-bounded pigment granules in shrimp ovarian chromatophores.

Lossless filter for multiple repeats with bounded edit distance

Background: Identifying local similarity between two or more sequences, or identifying repeats occurring at least twice in a sequence, is an essential part in the analysis of biological sequences and of their phylogenetic relationship. Finding such fragments while allowing for a certain number of insertions, deletions, and substitutions, is however known to be a computationally expensive task, and consequently exact methods can usually not be applied in practice. Results: The filter TUIUIU that we introduce in this paper provides a possible solution to this problem. It can be used as a preprocessing step to any multiple alignment or repeats inference method, eliminating a possibly large fraction of the input that is guaranteed not to contain any approximate repeat. It consists in the verification of several strong necessary conditions that can be checked in a fast way. We implemented three versions of the filter. The first is simply a straightforward extension to the case of multiple sequences of an application of conditions already existing in the literature. The second uses a stronger condition which, as our results show, enable to filter sensibly more with negligible (if any) additional time. The third version uses an additional condition and pushes the sensibility of the filter even further with a non negligible additional time in many circumstances; our experiments show that it is particularly useful with large error rates. The latter version was applied as a preprocessing of a multiple alignment tool, obtaining an overall time (filter plus alignment) on average 63 and at best 530 times smaller than before (direct alignment), with in most cases a better quality alignment. Conclusion: To the best of our knowledge, TUIUIU is the first filter designed for multiple repeats and for dealing with error rates greater than 10% of the repeats length.

A cross-linguistic comparison of address pronoun use in four European languages: Intralingual and interlingual dimensions

As part of a major ongoing project, we consider and compare contemporary patterns of address pronoun use in four major European languages- French, German, Italian and Swedish. We are specifically interested in two major aspects: intralingual behaviour, that is, within the same language community, and interlingual dimensions of address pronoun use. With respect to the former, we summarize our key findings to date. We then give consideration in a more preliminary fashion to issues and evidence relevant to the latter.

Periodic or Bounded Solutions of Carathéodory Systems of Ordinary Differential Equations

In this paper we extend the guiding function approach to show that there are periodic or bounded solutions for first order systems of ordinary differential equations of the form x1 =f(t,x), a.e. epsilon[a,b], where f satisfies the Caratheodory conditions. Our results generalize recent ones of Mawhin and Ward.

Membrane-bounded nucleoids in microbial symbionts of marine sponges

In thin sections of resin-embedded samples of glutaraldehyde- and osmium tetroxide-fixed tissue from five genera of marine sponges, Stromatospongia, Astrosclera, Jaspis, Pseudoceratina and Axinyssa, cells of a bacteria-like symbiont microorganism which exhibit a membrane-bounded nuclear region encompassing the fibrillar nucleoid have been observed within the sponge mesohyl. The nuclear region in these cells is bounded by a single bilayer membrane, so that the cell cytoplasm is divided into two distinct regions. The cell wall consists of subunits analogous to those in walls of some Archaea. Cells of the sponge symbionts observed here are similar to those of the archaeal sponge symbiont Cenarchaeum symbiosum. (C) 1998 Federation of European Microbiological Societies. Published by Elsevier Science B.V. All rights reserved.

Asymptotic limits of a self-dual Ginzburg-Landau functional in bounded domains

In the author's joint paper [HJS] with Jest and Struwe, we discuss asymtotic limits of a self-dual Ginzburg-Landau functional involving a section of a line bundle over a closed Riemann surface and a connection on this bundle. In this paper, the author generalizes the above results [HJS] to the case of bounded domains.