CD-Systems of Restarting Automata

Die vorliegende Arbeit behandelt Restartautomaten und Erweiterungen von Restartautomaten. Restartautomaten sind ein Werkzeug zum Erkennen formaler Sprachen. Sie sind motiviert durch die linguistische Methode der Analyse durch Reduktion und wurden 1995 von Jancar, Mráz, Plátek und Vogel eingeführt. Restartautomaten bestehen aus einer endlichen Kontrolle, einem Lese/Schreibfenster fester Größe und einem flexiblen Band. Anfänglich enthält dieses sowohl die Eingabe als auch Bandbegrenzungssymbole. Die Berechnung eines Restartautomaten läuft in so genannten Zyklen ab. Diese beginnen am linken Rand im Startzustand, in ihnen wird eine lokale Ersetzung auf dem Band durchgeführt und sie enden mit einem Neustart, bei dem das Lese/Schreibfenster wieder an den linken Rand bewegt wird und der Startzustand wieder eingenommen wird. Die vorliegende Arbeit beschäftigt sich hauptsächlich mit zwei Erweiterungen der Restartautomaten: CD-Systeme von Restartautomaten und nichtvergessende Restartautomaten. Nichtvergessende Restartautomaten können einen Zyklus in einem beliebigen Zustand beenden und CD-Systeme von Restartautomaten bestehen aus einer Menge von Restartautomaten, die zusammen die Eingabe verarbeiten. Dabei wird ihre Zusammenarbeit durch einen Operationsmodus, ähnlich wie bei CD-Grammatik Systemen, geregelt. Für beide Erweiterungen zeigt sich, dass die deterministischen Modelle mächtiger sind als deterministische Standardrestartautomaten. Es wird gezeigt, dass CD-Systeme von Restartautomaten in vielen Fällen durch nichtvergessende Restartautomaten simuliert werden können und andererseits lassen sich auch nichtvergessende Restartautomaten durch CD-Systeme von Restartautomaten simulieren. Des Weiteren werden Restartautomaten und nichtvergessende Restartautomaten untersucht, die nichtdeterministisch sind, aber keine Fehler machen. Es zeigt sich, dass diese Automaten durch deterministische (nichtvergessende) Restartautomaten simuliert werden können, wenn sie direkt nach der Ersetzung einen neuen Zyklus beginnen, oder ihr Fenster nach links und rechts bewegen können. Außerdem gilt, dass alle (nichtvergessenden) Restartautomaten, die zwar Fehler machen dürfen, diese aber nach endlich vielen Zyklen erkennen, durch (nichtvergessende) Restartautomaten simuliert werden können, die keine Fehler machen. Ein weiteres wichtiges Resultat besagt, dass die deterministischen monotonen nichtvergessenden Restartautomaten mit Hilfssymbolen, die direkt nach dem Ersetzungsschritt den Zyklus beenden, genau die deterministischen kontextfreien Sprachen erkennen, wohingegen die deterministischen monotonen nichtvergessenden Restartautomaten mit Hilfssymbolen ohne diese Einschränkung echt mehr, nämlich die links-rechts regulären Sprachen, erkennen. Damit werden zum ersten Mal Restartautomaten mit Hilfssymbolen, die direkt nach dem Ersetzungsschritt ihren Zyklus beenden, von Restartautomaten desselben Typs ohne diese Einschränkung getrennt. Besonders erwähnenswert ist hierbei, dass beide Automatentypen wohlbekannte Sprachklassen beschreiben.

Lower Bounds for Nonforgetting Restarting Automata and CD-Systems of Restarting Automata

The nonforgetting restarting automaton is a generalization of the restarting automaton that, when executing a restart operation, changes its internal state based on the current state and the actual contents of its read/write window instead of resetting it to the initial state. Another generalization of the restarting automaton is the cooperating distributed system (CD-system) of restarting automata. Here a finite system of restarting automata works together in analyzing a given sentence, where they interact based on a given mode of operation. As it turned out, CD-systems of restarting automata of some type X working in mode =1 are just as expressive as nonforgetting restarting automata of the same type X. Further, various types of determinism have been introduced for CD-systems of restarting automata called strict determinism, global determinism, and local determinism, and it has been shown that globally deterministic CD-systems working in mode =1 correspond to deterministic nonforgetting restarting automata. Here we derive some lower bound results for some types of nonforgetting restarting automata and for some types of CD-systems of restarting automata. In this way we establish separations between the corresponding language classes, thus providing detailed technical proofs for some of the separation results announced in the literature.

CD-Systems of Restarting Automata Governed by Explicit Enable and Disable Conditions

We introduce a new mode of operation for CD-systems of restarting automata by providing explicit enable and disable conditions in the form of regular constraints. We show that, for each CD-system M of restarting automata and each mode m of operation considered by Messerschmidt and Otto, there exists a CD-system M' of restarting automata of the same type as M that, working in the new mode ed, accepts the language that M accepts in mode m. Further, we prove that in mode ed, a locally deterministic CD-system of restarting automata of type RR(W)(W) can be simulated by a locally deterministic CD-system of restarting automata of the more restricted type R(W)(W). This is the first time that a non-monotone type of R-automaton without auxiliary symbols is shown to be as expressive as the corresponding type of RR-automaton.

On CD-systems of stateless deterministic R-automata with window size one

We study cooperating distributed systems (CD-systems) of restarting automata that are very restricted: they are deterministic, they cannot rewrite, but only delete symbols, they restart immediately after performing a delete operation, they are stateless, and they have a read/write window of size 1 only, that is, these are stateless deterministic R(1)-automata. We study the expressive power of these systems by relating the class of languages that they accept by mode =1 computations to other well-studied language classes, showing in particular that this class only contains semi-linear languages, and that it includes all rational trace languages. In addition, we investigate the closure and non-closure properties of this class of languages and some of its algorithmic properties.

CD-Systems of Stateless Deterministic R(1)-Automata Governed by an External Pushdown Store

We study cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are governed by an external pushdown store. In this way we obtain an automata-theoretical characterization for the class of context-free trace languages.

On Globally Deterministic CD-Systems of Stateless R-Automata with Window Size One

It is known that cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 accept a class of semi-linear languages that properly includes all rational trace languages. Although the component automata of such a CD-system are all deterministic, in general the CD-system itself is not, as in each of its computations, the initial component and the successor components are still chosen nondeterministically. Here we study CD-systems of stateless deterministic restarting automata with window size 1 that are themselves completely deterministic. In fact, we consider two such types of CD-systems, the strictly deterministic systems and the globally deterministic systems.

Cd-rom del Parc Natural de s'Albufera. 'Cd-rom del Parque Natural de la Albufera'.

Resumen tomado de la publicación

Cambio climático : Clarity : una exposición sobre cambio climático en CD-ROM.

Este CD contiene una colección de 17 carteles, listos para ser impresos, sobre los impactos, las causas y las posibles soluciones del cambio climático. Para cada cartel, se adjunta información complementaria, también se incluyen direcciones de internet y sugerencias para desarrollar actividades relacionadas con el cambio climático. Estos recursos permiten que un centro educativo, una asociación cultural, un Ayuntamiento o cualquier otra organización interesada, pueda producir su propia exposición sobre cambio climático y mostrarla al público: amigos, padres y ciudadanos. Se propone al educador que se convierta en un activo divulgador sobre el cambio climático, ayudándo al alumno a conocer mejor el problema y a descubrir cómo pueden contribuir a resolverlo.

Mi primer CD de inglés.

Cinco centros (dos públicos, dos concertados y el CPR) y cinco profesores han participado en el proyecto cuyo objetivo fue diseñar y elaborar una aplicación informática en soporte CD Rom que sea el primer contacto entre el niño de educación Infantil y/o primer ciclo de Primaria y el idioma inglés. Se comenzó con un estudio de los intereses y motivaciones de los alumnos a los que se dirige la aplicación, análisis de las herramientas, creación de la estructura del CD (pantallas), diseño de los personajes de la aplicación y de los soportes, montaje de las animaciones, sonorización y doblaje, elaboración de scripts y compilación de la fase beta del CD y testeo de los diferentes sistemas operativos de Windows. El resultado es la aplicación informática en la que se aprende dentro de entornos de trabajo muy conocidos por los alumnos, a la vez de crear una herramienta multimedia para el profesorado de inglés de Educación Infantil y Primaria.La evaluación se ha llevado a cabo con una escala de 8 ítems y cinco grados (muy mala- muy buena), con valoración global muy buena..

Avaliação da limpeza de CDtrodo construídos a partir de CD de ouro gravável/fita adesiva de galvanoplastia

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Determinação simultânea de 'CD' e 'PB' e de 'CR' e 'NI' em plantas medicinais empregando a espectrometria de absorção atômica com amostragem direta de suspensões

Pós-graduação em Química - IQ

Purification and characterization of a 34-kDa, heat stable glycoprotein from Synadenium grantii latex: action on human fibrinogen and fibrin clot

Latex glycoprotein (LGP) from Synadenium grantii latex was purified by the combination of heat precipitation and gel permeation chromatography. LGP is a heat stable protein even at 80 degrees C showed a sharp single band both in SDS-PAGE as well as in native (acidic) PAGE. LGP is a monomeric protein appears as single band under reducing condition. It is a less hydrophobic protein showed sharp single peak in RP-HPLC with retention time of 13.3 m. The relative molecular mass of LGP is 34.4 kDa. CD spectrum of LGP explains less content of alpha-helix (7%), and high content of beta-pleated sheets (48%) and random coils (46%). The N-terminal sequence of LGP is D-F-P-S-D-W-Y-A-Y-E-G-Y-V-I-D-R-P-F-S. Purified LGP is a fibrinogen degrading protease hydrolyses all the three subunits in the order of Aalpha, Bbeta and gamma. The hydrolytic pattern is totally different from plasmin as well as thrombin. LGP reduces recalcification time from 165 to 30 s with citrated human plasma but did not show thrombin like as well as factor Xa-like activity. Although LGP induces procoagulant activity, it hydrolyses partially cross-linked fibrin clot. It hydrolyses all the subunits of partially cross-linked fibrin clot (alpha- chains, beta-chain and gamma-gamma dimer). LGP is a serine protease, inhibited by PMSF. Other serine protease inhibitors, aprotinin and leupeptin did not inhibit the caseinolytic activity as well as fibrinogenolytic activity. We report purification and characterization of a glycoprotein from Synadenium grantii latex with human fibrino(geno)lytic activity.