There are many competing techniques for specifying robot policies, each having advantages in different circumstances. To unify these techniques in a single framework, we use formal language as an intermediate representation for robot behavior. This links previously disparate techniques such as temporal logics and learning from demonstration, and it links data driven approaches such as semantic mapping with formal discrete event and hybrid systems models. These formal models enable system verification -- a crucial point for physical robots. We introduce a set of rewrite rules for hybrid systems and apply it automatically build a hybrid model for mobile manipulation from a semantic map. In the manipulation domain, we develop a new workspace interpolation methods which provides direct, non-stop motion through multiple waypoints, and we introduce a filtering technique for online camera registration to avoid static calibration and handle changing camera positions. To handle concurrent communication with embedded robot hardware, we develop a new real-time interprocess communication system which offers lower latency than Linux sockets. Finally, we consider how time constraints affect the execution of systems modeled hierarchically using context-free grammars. Based on these constraints, we modify the LL(1) parser generation algorithm to operate in real-time with bounded memory use.

Diss. Linköping : Univ., 2002.

For more than 30 years, the problem of providing a formal framework for modeling dialogues has been a topic of great interest for the scientific areas of Linguistics, Philosophy, Cognitive Science, Formal Languages, Software Engineering and Artificial Intelligence. In the beginning the goal was to develop a "conversational computer", an automated system that could engage in a conversation in the same way as humans do. After studies showed the difficulties of achieving this goal Formal Language Theory and Artificial Intelligence have contributed to Dialogue Theory with the study and simulation of machine to machine and human to machine dialogues inspired by Linguistic studies of human interactions. The aim of our thesis is to propose a formal approach for the study of dialogues. Our work is an interdisciplinary one that connects theories and results in Dialogue Theory mainly from Formal Language Theory, but also from another areas like Artificial Intelligence, Linguistics and Multiprogramming. We contribute to Dialogue Theory by introducing a hierarchy of formal frameworks for the definition of protocols for dialogue interaction. Each framework defines a transition system in which dialogue protocols might be uniformly expressed and compared. The frameworks we propose are based on finite state transition systems and Grammar systems from Formal Language Theory and a multi-agent language for the specification of dialogue protocols from Artificial Intelligence. Grammar System Theory is a subfield of Formal Language Theory that studies how several (a finite number) of language defining devices (language processors or grammars) jointly develop a common symbolic environment (a string or a finite set of strings) by the application of language operations (for instance rewriting rules). For the frameworks we propose we study some of their formal properties, we compare their expressiveness, we investigate their practical application in Dialogue Theory and we analyze their connection with theories of human-like conversation from Linguistics. In addition we contribute to Grammar System Theory by proposing a new approach for the verification and derivation of Grammar systems. We analyze possible advantages of interpreting grammars as multiprograms that are susceptible of verification and derivation using the Owicki-Gries logic, a Hoare-based logic from the Multiprogramming field.

<p>Two classes of recurrent neural network models are compared in this report, simple recurrent networks (SRNs) and sequential cascaded networks (SCNs) which are first- and second-order networks respectively. The comparison is aimed at describing and analysing the behaviour of the networks such that the differences between them become clear. A theoretical analysis, using techniques from dynamic systems theory (DST), shows that the second-order network has more possibilities in terms of dynamical behaviours than the first-order network. It also revealed that the second order network could interpret its context with an input-dependent function in the output nodes. The experiments were based on training with backpropagation (BP) and an evolutionary algorithm (EA) on the AnBn-grammar which requires the ability to count. This analysis revealed some differences between the two training-regimes tested and also between the performance of the two types of networks. The EA was found to be far more reliable than BP in this domain. Another important finding from the experiments was that although the SCN had more possibilities than the SRN in how it could solve the problem, these were not exploited in the domain tested in this project</p>

Two classes of recurrent neural network models are compared in this report, simple recurrent networks (SRNs) and sequential cascaded networks (SCNs) which are first- and second-order networks respectively. The comparison is aimed at describing and analysing the behaviour of the networks such that the differences between them become clear. A theoretical analysis, using techniques from dynamic systems theory (DST), shows that the second-order network has more possibilities in terms of dynamical behaviours than the first-order network. It also revealed that the second order network could interpret its context with an input-dependent function in the output nodes. The experiments were based on training with backpropagation (BP) and an evolutionary algorithm (EA) on the AnBn-grammar which requires the ability to count. This analysis revealed some differences between the two training-regimes tested and also between the performance of the two types of networks. The EA was found to be far more reliable than BP in this domain. Another important finding from the experiments was that although the SCN had more possibilities than the SRN in how it could solve the problem, these were not exploited in the domain tested in this project

In this thesis, we investigate the complexity of the membership problem for pattern languages. A pattern is a string over the union of the alphabets A and X, where X := {x_1, x_2, x_3, ...} is a countable set of variables and A is a finite alphabet containing terminals (e.g., A := {a, b, c, d}). Every pattern, e.g., p := x_1 x_2 a b x_2 b x_1 c x_2, describes a pattern language, i.e., the set of all words that can be obtained by uniformly substituting the variables in the pattern by arbitrary strings over A. Hence, u := cacaaabaabcaccaa is a word of the pattern language of p, since substituting cac for x_1 and aa for x_2 yields u. On the other hand, there is no way to obtain the word u' := bbbababbacaaba by substituting the occurrences of x_1 and x_2 in p by words over A. The problem to decide for a given pattern q and a given word w whether or not w is in the pattern language of q is called the membership problem for pattern languages. Consequently, (p, u) is a positive instance and (p, u') is a negative instance of the membership problem for pattern languages. For the unrestricted case, i.e., for arbitrary patterns and words, the membership problem is NP-complete. In this thesis, we identify classes of patterns for which the membership problem can be solved efficiently. Our first main result in this regard is that the variable distance, i.e., the maximum number of different variables that separate two consecutive occurrences of the same variable, substantially contributes to the complexity of the membership problem for pattern languages. More precisely, for every class of patterns with a bounded variable distance the membership problem can be solved efficiently. The second main result is that the same holds for every class of patterns with a bounded scope coincidence degree, where the scope coincidence degree is the maximum number of intervals that cover a common position in the pattern, where each interval is given by the leftmost and rightmost occurrence of a variable in the pattern. The proof of our first main result is based on automata theory. More precisely, we introduce a new automata model that is used as an algorithmic framework in order to show that the membership problem for pattern languages can be solved in time that is exponential only in the variable distance of the corresponding pattern. We then take a closer look at this automata model and subject it to a sound theoretical analysis. The second main result is obtained in a completely different way. We encode patterns and words as relational structures and we then reduce the membership problem for pattern languages to the homomorphism problem of relational structures, which allows us to exploit the concept of the treewidth. This approach turns out be successful, and we show that it has potential to identify further classes of patterns with a polynomial time membership problem. Furthermore, we take a closer look at two aspects of pattern languages that are indirectly related to the membership problem. Firstly, we investigate the phenomenon that patterns can describe regular or context-free languages in an unexpected way, which implies that their membership problem can be solved efficiently. In this regard, we present several sufficient conditions and necessary conditions for the regularity and context-freeness of pattern languages. Secondly, we compare pattern languages with languages given by so-called extended regular expressions with backreferences (REGEX). The membership problem for REGEX languages is very important in practice and since REGEX are similar to pattern languages, it might be possible to improve algorithms for the membership problem for REGEX languages by investigating their relationship to patterns. In this regard, we investigate how patterns can be extended in order to describe large classes of REGEX languages.

Electronic mail (e-mail) is an under-utilised resource of information and knowledge. It could be an important part of the larger so-called organisational memory (OM)—if it were not so disorganised and fragmented. The OM contains the knowledge of the organisation’s employees, written records, and data. This thesis is about organising and managing information in, and about, e-mail so as to make it retrievable and usable for task management purposes. The approach is user-centred and based on a conceptual model for task management. The model is designed to handle tasks that occur in the communications in an open distributed system, such as Internet e-mail. Both structured and unstructured tasks can be supported. Furthermore, the model includes management of desktop source information, which comprises the different electronically available sources in a user’s computer environment. The information from these is used in the model to sort information and thereby handle tasks and related information. Tasks are managed as conversations, that is, exchanges of messages. We present a language called Formal Language for Conversations (FLC), based on speech act theory, which is used to organise messages and relevant information for tasks. FLC provides the container for task-related information, as well as the context for managing tasks. The use of FLC is exemplified in two scenarios: scheduling a meeting and making conference arrangements. We describe a prototype based on the conceptual model. The prototype explicitly refines and supports the notion of threads, which are employed so as to give tasks a context. It integrates the use of FLC into the traditional threading mechanism of e-mail, in addition to matching on text in the body. An agent architecture is also described, which is used to harmonise the information in the heterogeneous desktop sources. Finally, human-readable filtering rules created by a machine learning algorithm are employed in the prototype. The prototype is evaluated with regard to its thread-matching capability, as well as the creation of usable and readable filtering rules. Both are deemed satisfactory.

Over the past 10 years, several synthetic biology research groups have proposed tools and domain-specific languages to help with the design of artificial DNA molecules. Community standards for exchanging data between these tools, such as the Synthetic Biology Open Language (SBOL), have been developed. It is increasingly important to be able to perform in silico simulation before the time and cost consuming wet lab realization of the constructs, which, as technology advances, also become in themselves more complex. By extending the concept of describing genetic expression as a language, we propose to model relations between genotype and phenotype using formal language theory. We use attribute grammars (AGs) to extract context-dependent information from genetic constructs and compile them into mathematical models, possibly giving clues about their phenotypes. They may be used as a backbone for biological Domain-Specific Languages (DSLs) and we developed a methodology to design these AG based DSLs. We gave examples of languages in the field of synthetic biology to model genetic regulatory networks with Ordinary Differential Equations (ODEs) based on various rate laws or with discrete boolean network models. We implemented a demonstration of these concepts in GenoCAD, a Computer Assisted Design (CAD) software for synthetic biology. GenoCAD guides users from design to simulation. Users can either design constructs with the attribute grammars provided or define their own project-specific languages. Outputting the mathematical model of a genetic construct is performed by DNA compilation based on the attribute grammar specified; the design of new languages by users necessitated the generation on-the-fly of such attribute grammar based DNA compilers. We also considered the impact of our research and its potential dual-use issues. Indeed, after the design exploration is performed in silico, the next logical step is to synthesize the designed construct's DNA molecule to build the construct in vivo. We implemented an algorithm to identify sequences of concern of any length that are specific to Select Agents and Toxins, helping to ensure safer use of our methods. / Ph. D.

Graph extension grammars provide a way to define graph languages. They consist of a regular tree grammar and an algebra. The regular tree grammar generates trees, so-called derivation trees. Those are evaluated by the algebra into a set of graphs. A graph extension grammar allows two kinds of operations: disjoint unions and extension operations. A disjoint union combines two graphs into one. An extension operations extends a given graph by creating new nodes and connecting them to nodes present in the given graph. In this process, context nodes allow references in the form of edges to arbitrary nodes in the argument graph. For matching context nodes with nodes in the argument graph, there are two methods: either they are matched by their label or the target node needs to satisfy a formula. Each method yields one type of graph extension grammar, namely one with context matching and one with logic. We investigate both types of grammars regarding their language theoretic properties. For graph extension grammars with context matching we prove a pumping lemma and a variant of Parikh's theorem. We show that the path languages generated by those grammars are regular, which implies the decidability of the finiteness and emptiness problem. We prove that their language class is not closed under intersection and there are inherently ambiguous languages under some condition. For graph extension grammars we show that they can simulate Turing machines and thus their path languages can be recursively enumerable but not context-sensitive. There is no pumping lemma for those languages and they can grow exponentially or even faster. In addition to considering language theoretic properties, we improve the previously known parsing algorithm and give a characterisation of all derivable graphs.

This is a qualitative research that draws Gee‟s Discourse analysis to understand how learners communicate their mathematical reasoning in a multilingual classroom in South Africa. The study involved a Grade 11 class of 25 learners in a township school East of Johannesburg. The research method used was a case study. Data was collected using classroom observations, and document analysis. The study has shown that learners communicate their mathematics reasoning up to a certain level. The way learners communicated their mathematical reasoning depended on the activities that were given by the textbook being used in the classroom, and the questions which the teacher asked during the lessons. From the findings of the study, recommendations were made: the assessment of how learners communicate their mathematical reasoning should have a basis, say the curriculum. If the curriculum states the level of mathematical reasoning which the learners at Grade 11 must reach, then the teacher will have to probe the learners for higher reasoning; mathematics classroom textbooks should be designed to enable learners communicate their mathematical reasoning. The teacher should ask learners questions that require learners to communicate their mathematical reasoning.