The specification of a decoder, i.e., a program that translates sentences from one natural language into another, is an intricate process, driven by the application and lacking a canonical methodology. The practical nature of decoder development inhibits the transfer of knowledge between theory and application, which is unfortunate because many contemporary decoders are in fact related to formal-language theory. This thesis proposes an algebraic framework where a decoder is specified by an expression built from a fixed set of operations. As yet, this framework accommodates contemporary syntax-based decoders, it spans two levels of abstraction, and, primarily, it encourages mutual stimulation between the theory of weighted tree automata and the application.

Thesis (MSc (Mathematical Sciences))--University of Stellenbosch, 2008. / Context-free grammars are well-studied and well-behaved in terms of decidability, but many real-world problems cannot be described with context-free grammars. Grammars with regulated rewriting are grammars with mechanisms to regulate the applications of rules, so that certain derivations are avoided. Thus, with context-free rules and regulated rewriting mechanisms, one can often generate languages that are not context-free. In this thesis we study grammars with regulated rewriting mechanisms. We consider problems in which context-free grammars are insufficient and in which more descriptive grammars are required. We compare bag context grammars with other well-known classes of grammars with regulated rewriting mechanisms. We also discuss the relation between bag context grammars and recognizing devices such as counter automata and Petri net automata. We show that regular bag context grammars can generate any recursively enumerable language. We reformulate the pumping lemma for random permitting context languages with context-free rules, as introduced by Ewert and Van der Walt, by using the concept of a string homomorphism. We conclude the thesis with decidability and complexity properties of grammars with regulated rewriting.

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-08-08T13:11:15Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) tese.pdf: 4855618 bytes, checksum: 717d268b142705bdc8ce106731a257db (MD5) / Made available in DSpace on 2016-08-08T13:11:15Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) tese.pdf: 4855618 bytes, checksum: 717d268b142705bdc8ce106731a257db (MD5) Previous issue date: 2016-03-28 / CAPEs / Proof assistants are software-based tools that are used in the mechanization of proof construction and validation in mathematics and computer science, and also in certified program development. Different such tools are being increasingly used in order to accelerate and simplify proof checking, and the Coq proof assistant is one of the most known and used. Language and automata theory is a well-established area of mathematics, relevant to computer science foundations and information technology. In particular, context-free language theory is of fundamental importance in the analysis, design and implementation of computer programming languages. This work describes a formalization effort, using the Coq proof assistant, of fundamental results of the classical theory of context-free grammars and languages. These include closure properties (union, concatenation and Kleene star), grammar simplification (elimination of useless symbols, inaccessible symbols, empty rules and unit rules), the existence of a Chomsky Normal Form for context-free grammars and the Pumping Lemma for context-free languages. To achieve this, several steps had to be fulfilled, including (i) understanding of the characteristics, importance and benefits of mathematical formalization, specially in computer science, (ii) familiarization with the underlying mathematical theories used in proof assistants, (iii) familiarization with the Coq proof assistant, (iv) review of the strategies used in the informal proofs of the main results of the context-free language theory and finally (iv) selection and adequation of the representation and proof strategies adopted in order the achieve the desired objectives. The result is an important set of libraries covering the main results of context-free language theory, with more than 500 lemmas and theorems fully proved and checked. This is probably the most comprehensive formalization of the classical context-free language theory in the Coq proof assistant done to the present date, and includes the remarkable result that is the formalization of the Pumping Lemma for context-free languages. The perspectives for the further development of this work are diverse and can be grouped in three different areas: inclusion of new devices and results, code extraction and general enhancements of its libraries. / Assistentes de prova são ferramentas de software que são usadas na mecanização da construção e da validação de provas na matemática e na ciência da computação, e também no desenvolvimento de programas certificados. Diferentes ferramentas estão sendo usadas de forma cada vez mais frequente para acelerar e simplificar a verificação de provas, e o assistente de provas Coq é uma das mais conhecidas e utilizadas. A teoria de linguagens e de autômatos é uma área bem estabelecida da matemática, com relevância para os fundamentos da ciência da computação e a tecnologia da informação. Em particular, a teoria das linguagens livres de contexto é de fundamental importância na análise, no projeto e na implementação de linguagens de programação de computadores. Este trabalho descreve um esforço de formalização, usando o assistente de provas Coq, de resultados fundamentais da teoria clássica das gramáticas e linguagens livres de contexto. Estes incluem propriedades de fechamento (união, concatenação e estrela de Kleene), simplificação gramatical (eliminação de símbolos inúteis, de símbolos inacessíveis, de regras vazias e de regras unitárias), a existência da Forma Normal de Chomsky para gramáticas livres de contexto e o Lema do Bombeamento para linguagens livres de contexto. Para alcançar estes resultados, diversas etapas precisaram ser cumpridas, incluindo (i) o entendimento das características, da importância e dos benefícios da formalização matemática, especialmente na ciência da computação, (ii) a familiarização com as teorias matemáticas fundamentais utilizadas pelos assistentes de provas, (iii) a familiarização com o assistente de provas Coq, (iv) a revisão das estratégias usadas nas provas informais dos principais resultados da teoria das linguagens livres de contexto e, finalmente, (v) a seleção e adequação das estratégias de representação e prova adotadas para permitir o alcance dos resultados pretendidos. O resultado é um importante conjunto de bibliotecas cobrindo os principais resultados da teoria das linguagens livres de contexto, com mais de 500 lemas e teoremas totalmente provados e verificados. Esta é provavelmente a formalização mais abrangente da teoria clássica das linguagens livres de contexto jamais feita no assistente de provas Coq, e inclui o importante resultado que é a formalização do Lema do Bombeamento para linguagens livres de contexto. As perspectivas para novos desenvolvimentos a partir deste trabalho são diversas e podem ser agrupadas em três áreas diferentes: inclusão de novos dispositivos e resultados, extração de código e aprimoramentos gerais das suas bibliotecas.

[pt] O estado de sítio constitui uma figura constitucional essencial à compreensão das estruturas políticas democráticas. Se por um lado é mecanismo de proteção da sociedade, alargando os limites da autoridade estatal para rápida ação em situações excepcionais, por outro pode ser instrumento legitimador de arbitrariedades e abusos intervencionistas. As freqüentes decretações de estado de sítio durante a Primeira República brasileira servem como um indicativo das vicissitudes que permeavam os poderes estatais e das tentativas de consolidar o regime republicano federativo no país. A partir da compreensão de que o fenômeno normativo jurídico do estado de sítio pode ser visto como um fenômeno lingüístico, o presente trabalho analisa o instituto constitucional, durante o referido período histórico, com base nas teorias de linguagem de viés culturalista desenvolvidas por Mikhail Bakhtin e Pierre Bourdieu. Para tanto, foram examinados discursos sobre o sítio produzidos nas esferas dos três poderes públicos federais, registrados, principalmente, nos anais da Assembléia Constituinte, do Senado Federal e da Câmara dos Deputados, em mensagens redigidas pelos Presidentes da República e em decisões do Supremo Tribunal Federal. O estudo desses materiais, que leva a concluir que as disputas pelos sentidos do estado de sítio foram marcadas por relações lingüísticas de poder simbólico e que o instituto funcionou como meio de configuração das estruturas políticas e jurídicas da Primeira República, está estruturado em três partes: a primeira dedicada aos trabalhos constituintes, a segunda ao processo de concretização dos dispositivos constitucionais e a terceira à reforma da Constituição aprovada em 1926. / [en] Understanding the constitutional precept of the state of siege is essential to understanding the democratic political structures. If, on the one hand, it is a mechanism for the society s protection, thus broadening the limits of the state authority for a quick action in exceptional situations, then on the other hand it can be a legitimizing instrument of arbitrariness and interventionist abuses. The frequent declarations of state of siege during Brazil s First Republic can indicate the vicissitudes that used to permeate the state powers and the attempts to consolidate the federative republican regime in the country. Given that the normative juridical phenomenon of the state of siege can be seen as a linguistic phenomenon, the current work analyses the constitutional institution during the aforementioned period, based on the language theories of Mikhail Bakhtin and Pierre Bourdieu and their culturalist bias. Discourses on the state of siege produced by the three branches of the federal powers - mostly registered in the annals of the Constituent Assembly, the Senate and the House of Deputies, presidential messages and Supreme Court decisions - have been examined. The study of these materials is structured in three parts - the first, dedicated to the making of a new constitution, the second, concerning the solidification process of the constitutional rules and the third, dealing with the 1926 constitutional reform - and leads to the conclusion that the disputes on the meanings of state of siege were characterized by linguistic relations of symbolic power and that this institution worked as a means to configure the political and juridical institutions of the First Republic.

Abstract The purpose of this study is to analyse the reading- and writing-approaches: the LTG-method and the whole language-theory. The attention is to perform a comparative literate-study to distinguish their similarities and differences, and examine which one of the approaches that is most clearly anchored in the syllabus of the subject Swedish. The starting-point of the study is the questions: Which similarities respectively differences have the LTG-method and the whole language-theory? Which one of these theories is most clearly anchored in the syllabus of the subject Swedish? The study has shown that both the whole language-theory and the LTG-method can anchor in the syllabus for Swedish. However the whole language-theory has stronger hold in the syllabus, as the whole language emphasises the meaning of literature for reading- and writing-learning, and considers the pupils reflection during their learning-process and conquered knowledge-goal. The whole language-theory and the LTG-method have a number of similarities and emanate from similar influences. Finally I insinuate that the LTG-method could be a part or a direction under the parasol of the whole language-theory. / Sammandrag Syftet med studien är att studera läs- och skrivlärorna LTG-metoden och whole language-teorin. Avsikten är att utföra en komparativ litteraturstudie, för att urskilja de bådas likheter och olikheter, samt undersöka vilken av dem som är tydligast förankrad i kursplanen för svenska. Studiens utgångspunkt är frågeställningarna: Vilka likheter respektive skillnader har LTG och whole language-teorin? Vilken av dessa teorier finns tydligast förankrad i kursplanen för svenska? Studien har visat att såväl whole language-teorin som LTG-metoden kan förankras i kursplanen för svenska. Dock har whole language-teorin starkare fäste i kursplanen, då whole language-teorin betonar litteraturens betydelse för läs- och skrivinlärning, samt behandlar elevernas reflektion under deras inlärningsprocess och erövrade kunskapsmål. Whole language-teorin och LTG-metoden har en rad beröringspunkter, samt utgår från liknande influenser. Slutligen antyder jag att LTG-metoden skulle kunna vara en del eller en riktning under whole language-teorins parasoll.

Computer security is and will always be a critical area that affects everyone. Despite all the efforts made to build safer systems and test them, however, new vulnerabilities and vulnerabilities are still emerging and creating the impression of tilting at windmills. Partial justification of the current state, but also possible solutions, brings in many respects an extraordinary view of security through formal language theory. Emphasis should be put on a more responsible approach to the recognition and processing of inputs, which are often the gateway to many attacks. In this paper, we will get acquainted with this trend and its recommendations for development and will then introduce a new method of detecting SQL injection attacks built on its foundations.

This work describes models of modern language theory - finite automata, regular grammars and regular expressions. A web application converting among these models is implemented.

The purpose of this thesis is to investigate whether young people with neuropsychiatric disabilities feel that they have a spiritual longing. The research questions are also about what young people experience that which their spiritual longing is expressed and what conditions and obstacles exist to meet their longing and needs. With the help of role theory, language theory, and the theory of the illusionist world, new knowledge about young people's spiritual longing is gained.   The essay uses a qualitative method and collects empirical data by having two (2) group interviews, the first was with key people who are active in the business. And the second interview was with some young people who are active in the same business. With the help of the key people, broader knowledge has been achieved. By interviewing young people, their spiritual longing has been identified.   The essay shows that young people have a spiritual longing and that it must be allowed to take place and be taken seriously. The young people and the key people show signs that a language and an expression of spiritual longing is something that needs to be explored and developed. The essay concludes that young people have a spiritual longing and there are good conditions for further development, but more knowledge is needed when dealing with young people and their spiritual longing. The Church of Sweden has come a long way on its journey to a community, but there are still unexplored paths to follow.

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.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.