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.

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.

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.

Relations and Transductions Realized by Restarting Automata

Gegenstand der vorliegenden Arbeit ist die Analyse verschiedener Formalismen zur Berechnung binärer Wortrelationen. Dabei ist die Grundlage aller hier ausgeführten Betrachtungen das Modell der Restart-Automaten, welches 1995 von Jancar et. al. eingeführt wurde. Zum einen wird das bereits für Restart-Automaten bekannte Konzept der input/output- und proper-Relationen weiterführend untersucht, sowie auf Systeme von zwei parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (PC-Systeme) erweitert. Zum anderen wird eine Variante der Restart-Automaten eingeführt, die sich an klassischen Automatenmodellen zur Berechnung von Relationen orientiert. Mit Hilfe dieser Mechanismen kann gezeigt werden, dass einige Klassen, die durch input/output- und proper-Relationen von Restart Automaten definiert werden, mit den traditionellen Relationsklassen der Rationalen Relationen und der Pushdown-Relationen übereinstimmen. Weiterhin stellt sich heraus, dass das Konzept der parallel kommunizierenden Automaten äußerst mächtig ist, da bereits die Klasse der proper-Relationen von monotonen PC-Systemen alle berechenbaren Relationen umfasst. Der Haupteil der Arbeit beschäftigt sich mit den so genannten Restart-Transducern, welche um eine Ausgabefunktion erweiterte Restart-Automaten sind. Es zeigt sich, dass sich insbesondere dieses Modell mit seinen verschiedenen Erweiterungen und Einschränkungen dazu eignet, eine umfassende Hierarchie von Relationsklassen zu etablieren. In erster Linie seien hier die verschiedenen Typen von monotonen Restart-Transducern erwähnt, mit deren Hilfe viele interessante neue und bekannte Relationsklassen innerhalb der längenbeschränkten Pushdown-Relationen charakterisiert werden. Abschließend wird, im Kontrast zu den vorhergehenden Modellen, das nicht auf Restart-Automaten basierende Konzept des Übersetzens durch Beobachtung ("Transducing by Observing") zur Relationsberechnung eingeführt. Dieser, den Restart-Transducern nicht unähnliche Mechanismus, wird im weitesten Sinne dazu genutzt, einen anderen Blickwinkel auf die von Restart-Transducern definierten Relationen einzunehmen, sowie eine obere Schranke für die Berechnungskraft der Restart-Transducer zu gewinnen.

From Genetic Algorithms to Efficient Organization

The work described in this thesis began as an inquiry into the nature and use of optimization programs based on "genetic algorithms." That inquiry led, eventually, to three powerful heuristics that are broadly applicable in gradient-ascent programs: First, remember the locations of local maxima and restart the optimization program at a place distant from previously located local maxima. Second, adjust the size of probing steps to suit the local nature of the terrain, shrinking when probes do poorly and growing when probes do well. And third, keep track of the directions of recent successes, so as to probe preferentially in the direction of most rapid ascent. These algorithms lie at the core of a novel optimization program that illustrates the power to be had from deploying them together. The efficacy of this program is demonstrated on several test problems selected from a variety of fields, including De Jong's famous test-problem suite, the traveling salesman problem, the problem of coordinate registration for image guided surgery, the energy minimization problem for determining the shape of organic molecules, and the problem of assessing the structure of sedimentary deposits using seismic data.

Confianza inversionista: inversión extranjera directa en Colombia. Sector minero-energético, seguros, comercio, restaurantes y turismo. Periodo 2002-2010

Es preciso destacar que el periodo comprendido entre 2002 y 2010 bajo el mandato del ex presidente Álvaro Uribe, consolida una serie de políticas de Estado; además de la creación y reestructuración de nuevos entes reguladores. Así mismo, muestra un ambiente y clima propicio para incentivar la Inversión Extranjera Directa (IED) y activar las locomotoras productivas del país.

Análisis de la transformación de las relaciones militares entre Turquía e Israel a partir de la ruptura de la alianza bilateral generada por el ataque a la Flotilla de Gaza. Período 2008 a 2011

Amenazas como Siria, Irán y el PKK fueron relevantes al momento de forjar una alianza entre Turquía e Israel a mediados de los noventa. Con la firma de varios acuerdos en el ámbito militar se fortaleció la relación bilateral en materia de seguridad. Sin embargo, la llegada de un nuevo gobierno a Turquía en 2002 generó un cambio en materia de política exterior, especialmente con Israel. La monografía sustentada bajo los postulados de la Teoría del Balance de las Amenazas concluye que la ruptura de la alianza se dio por el cambio en la política exterior de seguridad turca, el bloqueo a Gaza por parte de Israel en 2008 y el ataque a la Flotilla de Gaza en 2010, conduciendo a una transformación en los acuerdos militares pactados para la seguridad y estabilidad de ambos países en la región de Medio Oriente.

Transparent Provenance Derivation for User Decisions

It is rare for data's history to include computational processes alone. Even when software generates data, users ultimately decide to execute software procedures, choose their configuration and inputs, reconfigure, halt and restart processes, and so on. Understanding the provenance of data thus involves understanding the reasoning of users behind these decisions, but demanding that users explicitly document decisions could be intrusive if implemented naively, and impractical in some cases. In this paper, therefore, we explore an approach to transparently deriving the provenance of user decisions at query time. The user reasoning is simulated, and if the result of the simulation matches the documented decision, the simulation is taken to approximate the actual reasoning. The plausibility of this approach requires that the simulation mirror human decision -making, so we adopt an automated process explicitly modelled on human psychology. The provenance of the decision is modelled in OPM, allowing it to be queried as part of a larger provenance graph, and an OPM profile is provided to allow consistent querying of provenance across user decisions.

Pesquisa orientada a resultado : proposta de um método estruturado para disponibilizar uma nova tecnologia para o mercado : um caso aplicado ao projeto etanol de 2ª geração

Esta dissertação de mestrado teve como objetivo principal propor um método estruturado suportado for ferramentas gerenciais que permitisse orientar e sistematizar o desenvolvimento de um projeto de pesquisa na disponibilização de uma nova tecnologia para o mercado. O “Projeto Etanol de 2ª Geração”, etanol produzido a partir de biomassas lignocelulósicas, aqui selecionado para estudo de caso, foi extraído da carteira de projetos do Centro de Tecnologia Canavieira (CTC). O método estruturado sugerido é constituído, fundamentalmente, por oito requisitos arranjados de forma cronológica ao longo do desenvolvimento do projeto, que visam auxiliar na prospecção, entendimento, avaliação, valoração, priorização, planejamento e implantação de, por exemplo, uma tecnologia inovadora, otimizando tempo, capital e recursos humanos aplicados. Um dos principais pontos do método proposto refere-se à escolha adequada das ferramentas gerenciais a serem utilizadas em cada requisito (brainstorm, análise de patentes, painel de especialistas, análise SWOT, dentre outras). O êxito na aplicação do método requer o entendimento de todos os (potenciais) efeitos, inclusive os colaterais, no processo como um todo. Ou seja, uma vez que toda ferramenta gerencial apresenta pontos fortes e fracos, o importante é adaptá-las ao sistema de negócio e não vice-versa. A partir do gerenciamento do projeto por um gestor com domínio das ferramentas gerenciais, a escolha destas ocorre de forma dinâmica, onde a cada passo de avaliação novas ferramentas (simples e/ou complexas) podem ser incluídas ou excluídas da matriz do método. Neste trabalho ficou demonstrada a importância de se trabalhar com métodos estruturados e flexíveis, que permitem retroalimentação de informações geradas internamente durante o desenvolvimento da pesquisa ou advindas de fontes externas. O projeto Etanol de 2ª Geração do CTC vem aplicando o método proposto em seu desenvolvimento e obtendo grande êxito em seus resultados, uma vez que a equipe envolvida permanece focada no objetivo principal, obedecendo prazos e recursos inicialmente definidos, com constância do propósito do projeto, sem retrocesso ou recomeço.

Complex mating behavior in Adelosgryllus rubricephalus (Orthoptera, Phalangopsidae, Grylloidea)

Descrevemos o comportamento reprodutivo de Adelosgryllus rubricephalus Mesa & Zefa, 2004. em observações realizadas em laboratório verificamos a seguinte seqüência no comportamento de acasalamento: (1) reconhecimento sexual por antenação; (2) corte, em que o macho volta seu abdômen em direção à fêmea, vibra as antenas médio-lateralmente, treme o corpo ântero-posteriormente e estridula intermitentemente, enquanto a fêmea receptiva toca a ponta do abdômen, os cercos e os fêmures posteriores do macho, com seus palpos ou tarsos anteriores; o macho então fica imóvel por alguns segundos, expõe o espermatóforo e ambos retomam a seqüência comportamental descrita acima; (3) cópula: o macho coloca-se sob a fêmea, com suas tégminas inclinadas para frente, anexa sua genitália à dela e promove a transferência do esperma; a fêmea desce de cima do macho e ocorre brevemente a posição end-to-end durante a separação do casal; (4) pós-cópula: não há comportamento de guarda; o macho retém o espermatóforo e o ingere. Quantificamos o intervalo de tempo das principais etapas do acasalamento e discutimos suas possíveis implicações no comportamento observado.

Reproductive technology in domestic carnivorous

Background: The delay in development of artificial reproduction techniques on carnivorous could be due to countless reasons, but the lack of commercial interest is probably the most important one. The majority of canines are small structures, canidae are extremely fertile and a great number of species are adapted to domestication or captivity. Finally, the canine gamete physiology presents a difficult adaptation of technology knowledge obtained from other species. Furthermore, domestic felines are animals of company and there is no interest in reproducing them in a large scale, as it has been observed in other domestic animals, however, besides of being a valuable model for the development of in vitro techniques, the domestic cat is also used as an embryo receptor for different species of small wild felines due to physiological similarities among them, in vitro embrionary development, Review: It was reviewed the main insights about the reproductive physiology in female dogs, in vitro oocytary maturation (IVM), pregnancy and conception rate with dogs' frozen/unfrozen semen and PIV in domestic cats. The majority of mammal oocytes restart meiosis spontaneously after ovulation and reaches MII in artificial environment; in an in vitro maturation system in bovines, around 90% of oocytes complete their maturation, although its development capacity can be reduced subsequently. The success of IVM in canidae have been limited, with maturation rate varying from 0 to 58%, usually around 20%. The greatest difficulties include oocyte quality, hormonal environment, protein supplementation, cumulus / oocyte cell interaction, donor breed and age, culture systems, oxygen tension, amino acids, growth factor and sequential means. The freezing process reduces the quality of the semen, firstly because it reduces the number of living sperms and secondly because freezing produces cell modifications that could alter the sperm motility, longevity, integrity of membranes and its fertilizing capacity. Conclusion: Nowadays, several researches are being performed with the aim of increasing viability after dogs' and cats' semen is unfrozen, using extenders, cryoprotectors, freezing and unfreezing curves, addition of antioxidant substances. The aim of this text is to inform about the improvements obtained on the artificial reproduction techniques, emphasizing the oocytary maturation in female dogs, semen cryopreservation and artificial insemination in domestic dogs and cats.

Transaction scheduling using dynamic conflict avoidance

Software transaction memory (STM) systems have been used as an approach to improve performance, by allowing the concurrent execution of atomic blocks. However, under high-contention workloads, STM-based systems can considerably degrade performance, as transaction conflict rate increases. Contention management policies have been used as a way to select which transaction to abort when a conflict occurs. In general, contention managers are not capable of avoiding conflicts, as they can only select which transaction to abort and the moment it should restart. Since contention managers act only after a conflict is detected, it becomes harder to effectively increase transaction throughput. More proactive approaches have emerged, aiming at predicting when a transaction is likely to abort, postponing its execution. Nevertheless, most of the proposed proactive techniques are limited, as they do not replace the doomed transaction by another or, when they do, they rely on the operating system for that, having little or no control on which transaction to run. This article proposes LUTS, a lightweight user-level transaction scheduler. Unlike other techniques, LUTS provides the means for selecting another transaction to run in parallel, thus improving system throughput. We discuss LUTS design and propose a dynamic conflict-avoidance heuristic built around its scheduling capabilities. Experimental results, conducted with the STAMP and STMBench7 benchmark suites, running on TinySTM and SwissTM, show how our conflict-avoidance heuristic can effectively improve STM performance on high contention applications. © 2012 Springer Science+Business Media, LLC.

Formulação do controle preventivo em sistemas de distribuição de energia elétrica baseada na lógica fuzzy e redes neurais

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

Músicos conectados, fãs colaborativos: uma análise do site MySpace

Pós-graduação em Comunicação - FAAC