The present work proposes visibly pushdown transducers (VPTs) for defining transformations of documents with a nesting structure. We show that this subclass of pushdown transducers enjoy good properties. Notably, we show that functionality is decidable in PTime and k-valuedness in co-NPTime. While this class is not closed under composition and its type checking problem against visibly pushdown automata is undecidable, we identify a subclass, the well-nested VPTs, closed under composition and with a decidable type checking problem. Furthermore, we show that the class of VPTs is closed under look-ahead, and that the deterministic VPTs with look-ahead characterize the functional VPTs transductions. Finally, we investigate the resources necessary to perform transformations defined by VPTs. We devise a memory efficient algorithm. Then we show that it is decidable whether a VPT transduction can be performed with a memory that depends on the level of nesting of the input document but not on its length. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

This thesis presents a novel Dynamic Gesture Language Recognition (DGLR) system for human-robot and inter-robot communication. We developed and implemented an experimental setup consisting of a humanoid robot/android able to recognize and execute in real time all the arm gestures of the Dynamic Gesture Language (DGL) in similar way as humans do. Our DGLR system comprises two main subsystems: an image processing (IP) module and a linguistic recognition system (LRS) module. The IP module enables recognizing individual DGL gestures. In this module, we use the bag-of-features (BOFs) and a local part model approach for dynamic gesture recognition from images. Dynamic gesture classification is conducted using the BOFs and nonlinear support-vector-machine (SVM) methods. The multiscale local part model preserves the temporal context. The IP module was tested using two databases, one consisting of images of a human performing a series of dynamic arm gestures under different environmental conditions and a second database consisting of images of an android performing the same series of arm gestures. The linguistic recognition system (LRS) module uses a novel formal grammar approach to accept DGL-wise valid sequences of dynamic gestures and reject invalid ones. LRS consists of two subsystems: one using a Linear Formal Grammar (LFG) to derive the valid sequence of dynamic gestures and another using a Stochastic Linear Formal Grammar (SLFG) to occasionally recover gestures that were unrecognized by the IP module. Experimental results have shown that the DGLR system had a slightly better overall performance when recognizing gestures made by a human subject (98.92% recognition rate) than those made by the android (97.42% recognition rate).

Orientador: Fernando Antônio Campos Gomide / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-18T15:47:57Z (GMT). No. of bitstreams: 1 Fuini_MateusGuilherme_M.pdf: 2245163 bytes, checksum: de5163a887c624c4488ae7be6adde00a (MD5) Previous issue date: 2006 / Resumo: Neste trabalho utilizam-se as teorias de Linguagem Formal Nebulosa e da Computacional das Percepções de Zadeh para definir buscas em uma base de dados gráfica. A descrição dos elementos gráficos a serem identificados é codificada por meio de sentenças aceitas por uma gramática nebulosa e definida sobre um conjunto de símbolos gráficos terminais reconhecidos por rotinas computacionais específicas. Esses símbolos terminais rotulam a imagem a ser pesquisada. A teoria da Percepção Computacional é usada para permitir que o usuário defina as relações espaciais a serem partilhadas pelos elementos gráficos na cena a ser pesquisada. Os resultados obtidos com buscas realizadas em uma base de dados gráfica com 22000 desenhos mostram que o sistema proposto fornece uma alternativa interessante para solução de buscas em bancos de dados visuais / Abstract: In this work, Fuzzy Formal Language techniques and Zadeh's Computational Theory of Perceptions are used to allow the user to query graphic data bases. The description of the graphic elements to be searched is encoded by means of fuzzy sentences accepted by a fuzzy grammar defined over a set of graphic primitives recognized by specific computational routines aimed to label different primitive graphic components of a given image. The Computational Theory of Perceptions is used to allow the user to specify the required spatial relations to be shared by the selected in the graphic scenes to be selected. The results obtained by querying a 22000 graphic scene data base support the claim that our approach provides a interesting solution for querying visual data bases / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

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.

No description available.

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 thesis introduces new models for formal languages, the m-limited state   grammar and the deep pushdown automaton. Their basic definitions are presented,   so is their mutual equivalence and the characteristics of the language family they describe.   Following, a parsing method based on these models is presented. The method is an extension   of a similar method used for context-free languages, the table driven parsing.   The final part of the thesis describes the implementation of a parser based on the method.

No description available.

No description available.

This thesis is situated at the boundary between formal language theory, algebra, and natural language processing (NLP). NLP knows a wide range of language models: from the simple n-gram models to the recently successful large language models (LLM). Formal approaches to NLP view natural languages as formal languages, i.e., infinite sets of strings, where each phrase is seen as a string, and they seek finite descriptions of these sets. Beyond language modeling, NLP deals with tasks such as syntactic analysis (or parsing), translation, information retrieval, and many others. Solving such tasks using language models involves two steps: Given a phrase of natural language, the model first builds a representation of the phrase and then computes the solution from that representation. Formal language models usually employ trees or similar structures as representations, whose evaluation to output values can be elegantly described using algebra. Chomsky introduced phrase structure grammars, which describe a process of generating strings using rewriting rules. For modeling natural language, these rules follow an important aspect of its syntax: constituency, i.e., the hierarchical structure of phrases. The best known grammar formalism is given by context-free grammars (CFG). However, CFG fail to model discontinuities in constituency, where several non-adjacent parts of a phrase form a subphrase. For instance, the German sentence “ich war auch einkaufen” can be understood so that “ich auch” is a noun phrase; it is discontinuous because it is interleaved by the verb “war”. This problem can be solved by employing more expressive grammar formalisms such as linear context-free rewriting systems (LCFRS). There are also grammar formalisms that generate sets of trees, e.g., regular tree grammars (RTG). A similar formalisms exists with finite-state tree automata (FTA) whose semantics is defined in terms of accepting an input rather than generating it, but FTA and RTG have the same expressiveness. Universal algebra lets us view trees as elements of a term algebra, which can evaluated to values in another algebra by applying a unique homomorphism. For instance, the strings generated by a CFG can be obtained by evaluating trees over the rules of the CFG in this way. Parsing is the problem of computing the constituency structure of a given phrase. Due to the ambiguity of natural language, several such structures may exist. This problem can be extended by weights such as probabilities in order to compute, for instance, the best constituency structure. The framework of semiring parsing abstracts from particular weights and is instead parameterized by a semiring, whereby many NLP problems can be obtained by plugging in an appropriate semiring. However, the semiring parsing algorithm is only applicable to some problem instances. Weighted deductive parsing is a similar framework that employs a different algorithm, and thus its applicability differs. We introduce a very general language model in the form of the RTG-based language model (RTG-LM) which consists of an RTG and a language algebra. The RTG generates the constituency structures of a language and, inspired by the initial algebra semantics, the language algebra evaluates these structures to elements of the modeled language; we call these elements syntactic objects. Through the free choice of the language algebra, many common grammar formalisms, such as CFG and LCFRS, are covered. We add multioperator monoids, a generalization of semirings, as a weight algebra to RTG-LM and obtain weighted RTG-based language models (wRTG-LM). This lets us define an abstract weighted parsing problem, called the M-monoid parsing problem. Its inputs are a wRTG-LM 𝐺 and a syntactic object 𝑎, and it states to compute all representations that 𝐺 has for 𝑎 using the language algebra. Then, these representations are evaluated to values in the weight algebra, and the values of all these representations are summed to a single output value. We propose the M-monoid parsing algorithm to solve this problem. It generalizes both the semiring parsing algorithm and the weighted deductive parsing algorithm in a way that is inspired by Mohri's single-source shortest distance algorithm. We prove two sufficient conditions for the termination and correctness of our algorithm. We show that our framework covers semiring parsing, weighted deductive parsing, and other problems from NLP and beyond. In the second part of this thesis, we explore constituent tree automata (CTA), a generalization of FTA, as a language model that is tailored towards modeling discontinuitiy. We show several properties of CTA, including that their constituency parsing problem is an instance of our M-monoid parsing problem and can, for a large class of CTA, be solved by the M-monoid parsing algorithm. This thesis aims to contribute a unifying formal framework for the specification of language models and NLP tasks. Through our general M-monoid parsing algorithm, we also provide a means of investigating the algorithmic solvability of problems within this field.