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.

Universität und solidarische Ökonomie

RESUMO: A economia solidária é aqui apresentada como um movimento social emancipatório e como uma das formas de resistências das trabalhadoras e trabalhadores ao modelo de desenvolvimento capitalista. O movimento contemporâneo de economia solidária abrange o processo de produção, comercialização e finanças. A economia solidária é caracterizada pela posse coletiva dos meios de produção e pelo controle dos trabalhadores dos empreendimentos através de autogestão, cooperação e solidariedade. Os empreendimentos econômicos solidários se organizam sob a forma de cooperativas, associações e grupos informais. Um dos maiores desafios da economia solidária está no campo educativo, porque impõe a desconstrução dos princípios individualistas e privatistas preponderantes na maioria das relações econômicas, e exige a construção de outra cultura pautada na solidariedade. Nesse sentido, a pesquisa realizada, tem como objeto de estudo as metodologias de incubação fomentadas pelas universidades nas ações de economia solidária. Para isso, analisamos as experiências da Incubadora de Economia Solidária da Universidade Federal da Paraíba - Brasil e da Incubadora na Universidade de Kassel- Alemanha – Verein für Solidarische Ökonomie e.V. A pesquisa buscou conhecer e analisar as práticas de incubagem das universidades na economia solidária, como processos de mudança social. A coleta de informações foi realizada, tendo por base, uma revisão bibliográfica, relatórios das Incubadoras, registros fotográficos, observação participante e entrevistas semi-estruturadas. Os resultados da análise indicam que as metodologias de incubação na economia solidaria, por terem um caráter aberto e participativo, por considerarem os condicionamentos históricos e as diferentes culturas, fazem-nas portadoras de mudanças sociais. Esta metodologia pode ser utilizada por diferentes atores, em lugares e situações distintas. A pesquisa indica ainda, a centralidade da questão ecológica como elemento que poderá unificar o movimento internacional de economia solidária.