323,463 research outputs found
Boyd, S./Schewe, M. (Hrsg.) (2012), Welttheater übersetzen adaptieren inszenieren, Worldtheater translation adaptation production, Berlin, Schibri-Verlag.
No full textBoyd, S./Schewe, M. (Hrsg.) (2012), Welttheater übersetzen adaptieren inszenieren, Worldtheater translation adaptation production, Berlin, Schibri-Verlag.Boyd, S./Schewe, M. (Hrsg.) (2012), Welttheater übersetzen adaptieren inszenieren, Worldtheater translation adaptation production, Berlin, Schibri-Verlag
Minimising Good-For-Games Automata Is NP-Complete
No full textThis paper discusses the hardness of finding minimal good-for-games (GFG) Büchi, Co-Büchi, and parity automata with state based acceptance. The problem appears to sit between finding small deterministic and finding small nondeterministic automata, where minimality is NP-complete and PSPACE-complete, respectively. However, recent work of Radi and Kupferman has shown that minimising Co-Büchi automata with transition based acceptance is tractable, which suggests that the complexity of minimising GFG automata might be cheaper than minimising deterministic automata.
We show for the standard state based acceptance that the minimality of a GFG automaton is NP-complete for Büchi, Co-Büchi, and parity GFG automata. The proofs are a surprisingly straight forward generalisation of the proofs from deterministic Büchi automata: they use a similar reductions, and the same hard class of languages
Das Sicherheitsgefühl und die Polizei: darf die Polizei das Sicherheitsgefühl schützen?
No full textSchewe CS. Das Sicherheitsgefühl und die Polizei: darf die Polizei das Sicherheitsgefühl schützen?. Schriften zum öffentlichen Recht; 1132. Berlin: Duncker & Humblot; 2009
Stephen Boyd und Manfred Schewe: Welttheater: übersetzen, adaptieren, inszenieren - World Theatre: translation, adaptation, production.
No full textFischer S. Stephen Boyd und Manfred Schewe: Welttheater: übersetzen, adaptieren, inszenieren - World Theatre: translation, adaptation, production. Aigne. The online postgraduate journal of the College of Arts, Celtic Studies and Social Sciences. 2013;(4)
Büchi Complementation Made Tight
No full textThe precise complexity of complementing B\"uchi\ automata is an intriguing and long standing problem. While optimal complementation techniques for finite automata are simple -- it suffices to determinize them using a simple subset construction and to dualize the acceptance condition of the resulting automaton -- B\"uchi\ complementation is more involved. Indeed, the construction of an EXPTIME complementation procedure took a quarter of a century from the introduction of B\"uchi\ automata in the early s, and stepwise narrowing the gap between the upper and lower bound to a simple exponent (of for B\"uchi\ automata with states) took four decades. While the distance between the known upper () and lower () bound on the required number of states has meanwhile been significantly reduced, an exponential factor remains between them. Also, the upper bound on the size of the complement automaton is not linear in the bound of its state space. These gaps are unsatisfactory from a theoretical point of view, but also because B\"uchi\ complementation is a useful tool in formal verification, in particular for the language containment problem. This paper proposes a B\"uchi\ complementation algorithm whose complexity meets, modulo a quadratic () factor, the known lower bound for B\"uchi\ complementation. It thus improves over previous constructions by an exponential factor and concludes the quest for optimal B\"uchi\ complementation algorithms
Peter Lutzker (2007), The Art of Foreign Language Teaching
No full textIn den wissenschaftsfixierten Fremdsprachendidaktiken haben die Künste lange ein Schattendasein geführt. Derzeit allerdings mehren sich die Zeichen dafür, dass die Künste mehr ins Licht treten und den Boden bereiten helfen für eine neue, performative Fremdsprachendidaktik.1 Auf diesem Hintergrund soll Lutzkers umfangreicher Studie (478 S.) neue Beachtung geschenkt werden, denn der Autor macht auf die vielfältigen Verbindungslinien aufmerksam, die es seit antiker Zeit zwischen Lehre und Kunst gibt und liefert empirische Belege für die Effektivität eines von der (Theater-)Kunst inspirierten Lehrens und Lernens. Seine Studie könnte beispielsweise ein sinnvoller Bezugspunkt sein, um im Rahmen des 14. Kongresses der Deutschen Gesellschaft für Fremdsprachenforschung (Hamburg, 28.9 – 1.10. 2011) nach Antworten auf Fragen zu suchen, die für die Arbeitsgruppe 11 zum Schwerpunktthema Theatermethoden und Fremdsprachenunterricht formuliert wurden: „Sind die proklamierten Einflüsse der Theaterarbeit auf die Persönlichkeitsentwicklung und die Ausbildung von sprachlichen bzw. interkulturellen Kompetenzen messbar? Und wie müssen Forschungsinstrumente beschaffen sein, um diese komplexen und vielschichtigen Unterrichtsprozesse gegenstandsangemessen zu ergründen?”2 Lutzkers Studie besteht aus zwei Teilen. Im ersten trifft er zunächst die grundsätzliche Unterscheidung zwischen auf der einen Seite pädagogischen Konzepten, die sich an Modellen von Science and Business orientieren und auf der anderen Seite einem Verständnis von Lehren als Kunst. Die dominante ..
Even, S., Miladinović, D., Schmenk, B. (Hrsg.): Lernbewegungen inszenieren: Performative Zugänge in der Sprach-, Literatur- und Kulturdidaktik. Festschrift für Manfred Schewe zum 65. Geburtstag. Tübingen: Narr Francke Attempto, 2019
No full textHorstmann S. Even, S., Miladinović, D., Schmenk, B. (Hrsg.): Lernbewegungen inszenieren: Performative Zugänge in der Sprach-, Literatur- und Kulturdidaktik. Festschrift für Manfred Schewe zum 65. Geburtstag. Tübingen: Narr Francke Attempto, 2019. Informationen Deutsch als Fremdsprache. 2021;48(2-3):190-196
Front Matter, Table of Contents, Preface, Conference Organization
No full textFront Matter, Table of Contents, Preface, Conference Organizatio
Natural Colors of Infinite Words
No full textWhile finite automata have minimal DFAs as a simple and natural normal form,
deterministic omega-automata do not currently have anything similar. One reason
for this is that a normal form for omega-regular languages has to speak about
more than acceptance - for example, to have a normal form for a parity
language, it should relate every infinite word to some natural color for this
language. This raises the question of whether or not a concept such as a
natural color of an infinite word (for a given language) exists, and, if it
does, how it relates back to automata.
We define the natural color of a word purely based on an omega-regular
language, and show how this natural color can be traced back from any
deterministic parity automaton after two cheap and simple automaton
transformations. The resulting streamlined automaton does not necessarily
accept every word with its natural color, but it has a 'co-run', which is like
a run, but can once move to a language equivalent state, whose color is the
natural color, and no co-run with a higher color exists.
The streamlined automaton defines, for every color c, a good-for-games
co-B\"uchi automaton that recognizes the words whose natural colors w.r.t. the
represented language are at least c. This provides a canonical representation
for every -regular language, because good-for-games co-B\"uchi automata
have a canonical minimal (and cheap to obtain) representation for every
co-B\"uchi language
Priority Promotion with Parysian flair
No full textWe develop an algorithm that combines the advantages of Priority Promotion, that is one of the leading approaches to solving large parity games in practice, with the quasi-polynomial time guarantees offered by Parys' algorithm. Hybridising these algorithms sounds both natural and difficult, as they both generalise the classic recursive algorithm in different ways that appear to be irreconcilable: while the promotion transcends the call structure, the guarantees change on each level. We show that an interface that respects both is not only effective, but also efficient
- …
