Master thesis deals with L grammar systems. The basic types of grammar systems are studied. There are analyzed different types of L grammars and their use in field of plant development simulation. The work focuses on open L grammars. A parallel system consisting of open L grammars is designed. Communication takes place through the exchange of information between plants and their environment. Implemented is real kind of tree. Simulated is typical environment in which this kind of tree occurs normally. The system properties are examined from the point of view of simulation and the time-consuming interpretation of strings. At the end of this thesis there are described some other options of future development of the project together with the possibilities of using the proposed system.

Tato diplomová práce se zabývá zkoumáním nových verzí automatů a gramatik a je proto rozdělena do dvou částí. První část definuje a studuje čisté více zásobníkové automaty a navíc zavádí úplná uspořádání nad jejich zásobníky nebo zásobníkovými symboly. Práce dokazuje, že zavedená omezení snižují vyjadřovací sílu automatů. Ve druhé části práce jsou definovány a popsány nové derivační módy gramatik s rozptýleným kontextem, které zobecňují relaci přímé derivace. Je dokázáno, že jejich použití nesnižuje vyjadřovací sílu gramatik.

La représentation de phénomènes naturels fait partie des domaines les plus complexes et les plus actifs de la recherche en informatique graphique. Notre compréhension de la nature s'améliorant au fil des années, les chercheurs ne cessent de proposer des nouveaux modèles, toujours plus pertinents les uns que les autres, et permettant de reproduire les différents phénomènes naturels que nous pouvons observer autour de nous, dans la vie de tous les jours. Nous nous sommes intéressés à la représentation du fruit et des différents éléments qui le caractérisent. Le fruit est un objet complexe et, en fonction de la précision requise, sa conception à l'aide de logiciels de modélisation 3D peut très vite devenir compliquée. Notre modèle permet de générer une grande variété de fruits de formes différentes ainsi que les différents éléments de leur structure interne et ce, grâce à l'utilisation d'une seule grammaire. Au sein d'une même espèce, les fruits générés seront tous différents au niveau de leur forme, tout en restant semblables. La seconde partie de nos travaux porte quant à elle sur la représentation des imperfections géométriques qui sont propres aux fruits. Les fruits sont le résultat de l'enchaînement d'un très grand nombre de processus physiologiques complexes qui interagissent fortement entre eux. Lorsque le bon fonctionnement de l'un de ces processus est compromis, cette anomalie se matérialise sur le fruit par l'apparition de défauts au niveau de sa forme. Notre modèle propose une approche simple, basée sur l'utilisation de grammaires, qui permettent d'altérer soit la forme générale d'un fruit soit des parties de sa surface. / One of the largest areas of research in computer graphics deals with natural phenomena representation. Over the years, as our understanding of nature grew, researchers started to propose new ways of simulating the various natural phenomena that we can observe in our everyday life. In this thesis, we focused on the representation of fruits. The fruit is a complex object. Depending on the desired accuracy, modeling a 3D fruit using classic 3D modeling software can become very tedious. We propose a model for generating vast varieties of fruits as well as their internal structure, thanks to the use of a single formal grammar. Each fruit that will be generated using our method will have global features that characterize its species, but it will also have local variations that are specific to it. The second part of ou work involves the representation of geometrical imperfections along the fruit. The fruit is the result of a series of physiological processes that strongly interact with each other. When one of these processes does not work the way it should, this dysfunction is materialized in the form of a shape defect. Our model introduces a simple approach, based on the use of grammars, which will allow us to apply variations on fruits in order to generate various categories of shape defects.

Cette thèse porte sur un art martial, l’aikibudo, « fondé » au début des années 1980 par le Français Alain Floquet. Âgé de presque 80 ans, celui-ci tente, depuis quelques années, de transmettre progressivement la responsabilité technique de son école. Cette transmission intensifie des tensions entre les successeurs potentiels – ceux que nous avons appelés les maîtres. Ainsi, l’organisation de la discipline doit-elle se moderniser ou garder un caractère « traditionnel » ? Avec une forme technique plus éthérée ou plus réaliste ? Et quelle devrait-elle la place de chacun dans la future organisation ? De leur point de vue, les maîtres considèrent le plus souvent ces tensions comme des luttes d’ego ou encore des luttes de pouvoir. Il semble pourtant qu’elles ne relèvent pas que de la seule rationalité instrumentale. Telle est l’hypothèse générale de cette recherche. Pour mener à bien cette recherche, deux cadres théoriques jusqu’ici peu articulés ont été croisés : la sociologie pragmatique de Boltanski et Thévenot (1991) qui permet d’appréhender les arrière-plans axiologiques de ces tensions ; le programme dispositionnaliste proposé par Lahire (2012) qui s’attache aux dispositions des individus observés et aux contextes (macro et micro sociaux) dans lesquels ils agissent. L’enquête menée repose sur un volet qualitatif (observation participante, entretiens semi-directifs) et un volet quantitatif (analyse sociodémographique des pratiquants et questionnaire en ligne). Elle conduit à deux résultats principaux. Il en ressort d’abord que derrière l’apparente unité du discours des maîtres sur l’aikibudo, on peut distinguer trois modes d’engagement dans la discipline : l’engagement militaire, l’engagement artistique et l’engagement sportif. Chacun de ces modes d’engagement se traduit par des forme spécifiques de pratique, un attachement plus ou moins fort à la tradition, et un type de rapport de l’individu au groupe. De la sorte, on met en évidence la dimension morale des tensions dont l’enjeu est une reconfiguration et une redéfinition de la discipline au moment où le fondateur délègue progressivement la direction de son école. Par ailleurs, l’aikibudo n’est pas, pour ceux qui s’y engagent fortement, qu’un espace trivial de loisir. Il constitue le lieu central et symbolique d’une quête soi d’autant plus dense que l’individu a subi, préalablement, des expériences douloureuses, des formes d’humiliation ou de violence. Ainsi, les tensions apparaissent sous un autre jour. Leur virulence s’explique par le sens que les individus trouvent dans leur engagement dans l’aikibudo : une parabole de leur lutte pour la verticalité entendue comme un redressement et une élévation de soi. L’accès au statut de maître marque la reconnaissance de cette lutte que les haut-gradés mènent depuis plusieurs décennies. Mettre en doute leur qualité ou leur compétence de maître, c’est comme affecter ce qui fonde l’identité qu’ils ont pu construire, dans et au-delà de l’espace clos du dojo / This PhD thesis deals with a martial art – aikibudo – "founded" in the early 1980’s by the Frenchman Alain Floquet. Today, he is indeed 80 years old and has been passing on the technical charge of his "school" for a few years. But some tensions have grown between his successors – called "the masters" – who disagree on the future of aikibudo: should it become a traditional or a modern school? With an artistic or a realistic form? And what should the place of each one be in the future organization of the group? From their own point of view, the masters consider these tensions are caused by warring egos or power struggles. The general hypothesis of this work consists in showing that these tensions are not due to instrumental rationality alone. It is based on the crossing of two theoretical frameworks, namely the pragmatic sociology of Boltanski and Thevenot (1991) which enables to understand the axiological backgrounds of these tensions and the dispositionalist program of Lahire (2012) which focuses on the dispositions of some observed individuals and on the macro and micro-social contexts in which they interact. The study contains a qualitative part (participant observation and semi-leading interviews) and a quantitative one (practitioners’ sociodemographic analysis and an online questionnaire). There are two main results. Firstly, behind the visible unity of the Masters’ speeches on aikibudo, we can notice three types of commitment: a military commitment, an artistic commitment and an individualist (or athletic) commitment. Each of them implies specific practices, more or less powerful links to traditions and different forms of attachment of the individual to the group. This way, the moral dimension of the tensions becomes obvious. Their major issue is the redefinition and reconfiguration of the martial art as its founder is little by little delegating the running of his school. Secondly, aikibudo is not only a trivial space of leisure for those who are strongly engaged in it. It is also a central and symbolic quest of one’s self, all the more important that the individual has previously lived painful, humiliating or even violent experiences. Thus the tensions appear in a different way. Their virulence can be explained by the sense the individuals give to their commitment to aikibudo: a parable of their struggle for verticality in the sense of a recovery, an elevation of their selves. Accessing the rank of Master is like a gratitude for those at the top who have been struggling for decades. Doubting their skills as Masters affects the identity they have been building inside and outside the confined space of the dojo

Software components provide essential means to structure and organize software effectively. However, frequently, required component abstractions are not available in a programming language or system, or are not adequately combinable with each other. Invasive software composition (ISC) is a general approach to software composition that unifies component-like abstractions such as templates, aspects and macros. ISC is based on fragment composition, and composes programs and other software artifacts at the level of syntax trees. Therefore, a unifying fragment component model is related to the context-free grammar of a language to identify extension and variation points in syntax trees as well as valid component types. By doing so, fragment components can be composed by transformations at respective extension and variation points so that always valid composition results regarding the underlying context-free grammar are yielded. However, given a language’s context-free grammar, the composition result may still be incorrect. Context-sensitive constraints such as type constraints may be violated so that the program cannot be compiled and/or interpreted correctly. While a compiler can detect such errors after composition, it is difficult to relate them back to the original transformation step in the composition system, especially in the case of complex compositions with several hundreds of such steps. To tackle this problem, this thesis proposes well-formed ISC—an extension to ISC that uses reference attribute grammars (RAGs) to specify fragment component models and fragment contracts to guard compositions with context-sensitive constraints. Additionally, well-formed ISC provides composition strategies as a means to configure composition algorithms and handle interferences between composition steps. Developing ISC systems for complex languages such as programming languages is a complex undertaking. Composition-system developers need to supply or develop adequate language and parser specifications that can be processed by an ISC composition engine. Moreover, the specifications may need to be extended with rules for the intended composition abstractions. Current approaches to ISC require complete grammars to be able to compose fragments in the respective languages. Hence, the specifications need to be developed exhaustively before any component model can be supplied. To tackle this problem, this thesis introduces scalable ISC—a variant of ISC that uses island component models as a means to define component models for partially specified languages while still the whole language is supported. Additionally, a scalable workflow for agile composition-system development is proposed which supports a development of ISC systems in small increments using modular extensions. All theoretical concepts introduced in this thesis are implemented in the Skeletons and Application Templates framework SkAT. It supports “classic”, well-formed and scalable ISC by leveraging RAGs as its main specification and implementation language. Moreover, several composition systems based on SkAT are discussed, e.g., a well-formed composition system for Java and a C preprocessor-like macro language. In turn, those composition systems are used as composers in several example applications such as a library of parallel algorithmic skeletons.

This study investigated the possibility of procedural generation of skill trees which are similar to skill trees in contemporary video games. A set of randomly-selected skill trees from contemporary video games, from differ- ent game genres, was compiled, and an analysis was performed to extract relevant observations from the set. Using the observations, models for skill tree generation, and for skill tree comparison were proposed, and they were followed for the generation and analysis of the results. It was found that the method of Graph Grammars provided satisfying results compared to the set of skill trees from video games. Additionally, the other methods researched, L-Systems and Naive Randomized Graph Generation, while both may still require improvements discussed in the thesis in order to provide more satis- fying results, they may still be used for particular needs by game designers as they are. 1

Title: Application of hierarchical graph grammars in procedural 3D world gen- eration Author: Jakub Svoboda Abstract: Procedural content generation (PCG) is an often-used technique in video games. It allows us to generate large quantities and permutations of con- tent. A common problem in utilizing PCG in level design is that it is challenging to generate content close to what a human would create in overall quality and structure. One way of solving these problems is using graph grammars to rep- resent relations in the game world. Implementing a working graph generator using graph grammars and applying it to generate worlds is not very well docu- mented. This thesis will try to overcome this problem by implementing such a generator and extending it to use hierarchical graph grammars. The generator will be used to generate a 3D open world. The generator should be suitable for levels in other types of games. Keywords: procedural content generation, game development, hierarchical graphs, graph grammars, procedural level design

Tato disertační práce studuje synchronní formální systémy založené na gramatikách a převodnících a zkoumá jak jejich teoretické vlastnosti, tak i perspektivy praktických aplikací. Práce představuje nové koncepty a definice vycházející ze známých principů řízeného přepisování a synchronizace. Navrhuje alternativní způsob synchronizace bezkontextových gramatik, založený na propojení pravidel. Tento princip rozšiřuje také na řízené gramatiky, konkrétně gramatiky s rozptýleným kontextem a maticové gramatiky. Dále je představen na podobném principu založený nový druh převodníku, tzv. pravidlově omezený převodník. Jedná se o systém složený z konečného automatu a bezkontextové gramatiky. Práce prezentuje nové teoretické výsledky ohledně generativní a přijímajicí síly. Poslední část práce zkoumá možnosti lingvisticky orientovaných aplikací se zameřením na překlad přirozeného jazyka. Diskutuje a srovnává hlavní výhody nových modelů s využitím vybraných případových studií z českého, anglického a japonského jazyka pro ilustraci.

本論文提供了一個句子重組試題編製的環境，協助教師編製句子重組試題，同時學生也能夠在此編製環境中練習句子重組試題。 句子重組試題即是要求學生把試題給的一組詞彙組合成特定詞序的正確語句之題型，該試題類型可以檢驗學生對於句型和文法的知識。然而試題所給的詞彙集合往往除了可以組合成教師想要學生回答的正確語句之外，也可以組合成其它的合法語句。為了能辨識學生的回答，把這些合法語句以人工方式逐一建置為答案卻對出題教師造成了負擔。 我們建構了一個電腦輔助句子重組試題編製的環境來減輕出題教師的負擔。為了讓電腦可以恰當地判斷學生的回答，我們的編製環境限制了試題詞彙集的相對位置，藉此約束學生只能排出教師預設的特定答案。同時在出題教師建置試題答案時，我們的編製環境也試圖提供所有可能的合法詞序之語句，供出題教師參考。但本論文的研究經驗顯示要自動協助出題教師預示所有可能的合法詞序之語句卻是一件艱難的工作，而且這一研究問題與語法學有密切關係。 本論文以基礎詞組為主軸，透過合併詞組和史丹佛剖析器的操作建構出英文句子重組試題編製環境，供教師編輯與學生練習。同時，我們在論文中也提報了中文句子重組試題編製環境的初步探討。 / This thesis presents a computer assisted environment for authoring test items for sentence reconstruction. Not only the teacher can author the test items for sentence reconstruction, but also the student can practice the test items in this environment. A test item for sentence reconstruction asks the student to arrange the shuffled words in a correct order, and this type of tests can examine the knowledge of sentence patterns and grammars of the student. However, the rearranged sentence may match with not only the correct sentence that the teacher wants but also other sentences which are legal. But enumerating all possible legal and acceptable answers for judging the answer of the student manually makes the teacher taking a big load. We construct a computer assisted environment for authoring test items for sentence reconstruction to lighten the load of the teacher. For the purpose of judging the answer of the student by a computer easily, the relative locations of the words are restricted so that we can restrict the sentences that the student arranges. When the teacher provides the correct answers, we try to find and return all of the sentences which may be legal for the teacher's consideration. However, our experience shows that it is difficult to find all of the legal sentences for a given set of words, and this problem associates closely with a certain syntactic research work. This thesis depends on basic word groups to construct an environment of test item authoring for English sentence reconstruction by merging word groups and using the Stanford Parser, and report an initial study of an environment of test item preparation for Chinese sentence reconstruction.

The field of statistical machine translation has made tremendous progress due to the rise of statistical methods, making it possible to obtain a translation system automatically from a bilingual collection of text. Some approaches do not even need any kind of linguistic annotation, and can infer translation rules from raw, unannotated data. However, most state-of-the art systems do linguistic structure little justice, and moreover many approaches that have been put forward use ad-hoc formalisms and algorithms. This inevitably leads to duplication of effort, and a separation between theoretical researchers and practitioners. In order to remedy the lack of motivation and rigor, the contributions of this dissertation are threefold: 1. After laying out the historical background and context, as well as the mathematical and linguistic foundations, a rigorous algebraic model of machine translation is put forward. We use regular tree grammars and bimorphisms as the backbone, introducing a modular architecture that allows different input and output formalisms. 2. The challenges of implementing this bimorphism-based model in a machine translation toolkit are then described, explaining in detail the algorithms used for the core components. 3. Finally, experiments where the toolkit is applied on real-world data and used for diagnostic purposes are described. We discuss how we use exact decoding to reason about search errors and model errors in a popular machine translation toolkit, and we compare output formalisms of different generative capacity.