Search

We are developing a theory of probabilistic language learning in the context of robotic instruction in elementary assembly actions. We describe the process of machine learning in terms of the various events that happen on a given trial, including the crucial association of words with internal representations of their meaning. Of central importance in learning is the generalization from utterances to grammatical forms. Our system derives a comprehension grammar for a superset of a natural language from pairs of verbal stimuli like Go to the screw! and corresponding internal representations of coerced actions. For the derivation of a grammar no knowledge of the language to be learned is assumed but only knowledge of an internal language. We present grammars for English, Chinese, and German generated from a finite sample of about 500 commands that are roughly equivalent across the three languages. All of the three grammars, which are context-free in form, accept an infinite set of commands in the given language.

We present a new approach to formal language theory using Kolmogorov complexity. The main results presented here are an alternative for pumping lemma(s), a new characterization for regular languages, and a new method to separate deterministic context-free languages and nondeterministic context-free languages. The use of the new "incompressibility arguments" is illustrated by many examples. The approach is also successful at the high end of the Chomsky hierarchy since one can quantify nonrecursiveness in terms of Kolmogorov complexity.

A new way of associating a language with the computation of a P system is considered. A label is assigned to every rule in a P system, where the labels are chosen from a finite alphabet or \(\lambda .\) We associate a string, called control word, that is obtained by concatenating the labels of the rules in the transition sequence corresponding to a computation. We study the generative capacity of such control languages comparing them with family of languages such as regular, context-free, context-sensitive and recursively enumerable languages of Chomskian hierarchy.

The purpose of a Machine Translation (MT) system is to decode one language into another. Every language has its own different lexical and syntactic structure. A hybrid language does not have its own structure; it is an amalgamation of two or more languages in a sentence. To understand the structure and to decode a hybrid language into a formal language, hybrid parsing techniques are required. Hindi and English have Subject Object Verb (SOV) and Subject Verb Object (SVO) word orders, respectively. The basic requirement of parsers is to transform a SOV word order to a SVO word order and vice versa and Part of Speech (POS) tagging is essential for word grouping. The purpose of this paper is to bring out the concepts of parsers and POS tagging techniques to which hybrid translation can takes place to a formal language.

The following article is concerned with the problem of language diversity within the framework of Radical Minimalism (Krivochen 2011, 2012). How can the diversity and variation of languages be explained? For Noam Chomsky, language faculty in the narrow sense (FLN) is nothing but an “‘organ of the body,’ along with other cognitive systems. Our analysis of human language builds on Chomsky’s (1995, 2005, 2010) minimalist assumption that the design of language is grounded in conceptual necessity. Adopting this idea, we expect to find three factors that interact to determine (I-) languages attained: genetic endowment (the topic of Universal Grammar), experience, and principles that are language- or even organism-independent.” (Chomsky 2005:1). In the present article we provide some ideas about how generative research based on Radical Minimalism can contribute on a par with the typology of languages to a more profound and sound exploration of language variation. The scope of the paper is to compare the distribution of adverbs within the three domains of the clause in Czech and German. The aim of this paper is to show that the feature-based theory of adverb licensing is not able to handle the problem of adverb order variation. Instead, a more parsimonious approach based on the Theory of Radical Minimalism will be chosen. The paper is organized as follows: After some remarks on the role of Universal Grammar, Variation and Typology in section 1, section 2 introduces the theoretical background by introducing the principles and the core of Radical Minimalism, e.g. free unbounded merge, asymmetric c-command and the restrictions within the clause structure composition. In section 3, the distribution of adverbs in the middle field is discussed for Czech and German. In the last part, we introduce the so-called Late Adjunction Hypothesis that results in similar effects to the Early Spell-Out model argued for in our paper.

The edit-distance between two strings is the smallest number of operations required to transform one string into the other. The edit-distance problem for two languages is to find a pair of strings, each of which is from different language, with the minimum edit-distance. We consider the edit-distance problem for a regular language and a context-free language and present an efficient algorithm that finds an optimal alignment of two strings, each of which is from different language. Moreover, we design a faster algorithm for the edit-distance problem that only finds the minimum number of operations of the optimal alignment.

In the natural language processing and its related fields, the classic text representation methods seldom consider the role of the words order and long-distance dependency in the texts for the semantic representation. In this paper, we discussed current situation and problems of the statistical language models, especially for Head-driven statistical language model and Head-driven Phrase Structure Grammar (HPSG). And then the development and realization methods of the long-distance dependency language model simply introduced. At last graph-based long-distance dependency language model was proposed in the paper.

We discuss the problem of identifying inconsistencies in temporal requirements expressed as natural language text. We propose a partially automated approach that aims to minimize analysts' workload and improve accuracy. As one of the ingredients of the approach, we introduce a formal language to represent temporal requirements precisely and unambiguously. We call this language Temporal Action Language (TAL).

International audience; In this paper, we prove decidability properties and new results on the position of the family of languages generated by (circular) splicing systems within the Chomsky hierarchy. The two main results of the paper are the following. First, we show that it is decidable, given a circular splicing language and a regular language, whether they are equal. Second, we prove the language generated by an alphabetic splicing system is context-free. Alphabetic splicing systems are a generalization of simple and semi-simple splicing systems already considered in the literature.

We show interreducibility under (Turing) reductions of low polynomial degree between three families of problems parametrised by classes of formal languages: the problem of reachability in a directed graph constrained by a formal language, the problem of deciding whether or not the intersection of a language of some class with a regular language is empty, and the model checking problem for Propositional Dynamic Logic over some class of formal languages. This allows several decidability and complexity results to be transferred, mainly from the area of formal languages to the areas of modal logics and formal language constrained reachability.

A special class of context-sensitive generative languages (CSGLs) that can be used as an indexation in parallel computing is described. The languages are recursively generated, and the algorithm for interprocesses communication is based on the positive resolution of the post correspondence problem (PCP) within CSGLs. This fact follows from the main result that a constructed CSGL has a complete set of production rules, i.e. no new rule can be added to the set without destroying the integrity of the CSGL.

This paper presents a lexical analyser for inflected Arabic words. An augmented transition network (ATN) technique was used to represent the context-sensitive knowledge about the relation between a stem and inflectional additions. An exhaustive-search algorithm is developed to traverse the ATN, generating all possible interpretations of an inflected Arabic word. The arcs of the ATN are augmented with rules containing conditions and actions. More than one rule is associated with some arcs. The states of the ATN are represented by Pascal procedures.

This paper presents the application of a formal description language -- Van Wijngaarden Two-Level grammar -- to define the dynamic semantics of a block structured language consisting of several types of parameter passing mechanisms. We will show, in a fairly understandable, concise and clear fashion, that the metalinguistic formalism of Two-Level grammar is a fine descriptive device for this purpose.

In the IPTES project a dual language approach is proposed for overcoming both the problems derived from the use of a user-friendly, high-level, but not-formally-defined language and from a lower-level, formal, but difficult-to-use language. The approach uses a user-friendly, high-level language as user interface and a lower-level, formal language asmachine language. In this way the users can both access the IPTES environment through a nice interface and can profit from non-ambiguity-checks and proofs algorithms based on the formal kernel machine language. The correspondence between the two languages is built-in in the IPTES environment that provides a transparent mapping mechanism that relates the users specifications expressed by means of the high-level interface-language with the formal definitions expressed in the formal machine language.This paper presents the mapping mechanism that relates the current IPTES user interface (SA/RT (Ward and Mellor 1985)) with the IPTES machine language (high-level timed Petri nets (Ghezzi, Mandrioli, Morasca and Pezzé 1991)). As a side effect, it also presents the formal semantics of SA/RT defined by means of high-level timed Petri nets.

MathAbs (Mathematical Abstract language) is a system independent formal language for mathematical texts that can preserve its structure including the line of reasoning, proof steps and logical structure. By system independent, we mean that its formalism is not based on any specific logic, theory or proof assistant.MathAbs is intended only for machine manipulation and it is part of a system called MathNat[6], which provides a controlled language to write mathematical texts found in textbooks and published work. Here, MathAbs is used as an intermediary between the natural language of the mathematician and the formal language of the logician. We give here a detailed account of MathAbs, its justification, formal definition and semantics.

We have become so used to viewing natural language in computational terms that we need occasionally to remind ourselves of the methodological commitment this view entails. That commitment is this: we assume that to understand linguistic tasks—tasks such as recognizing sentences, determining their structure, extracting their meaning, and manipulating the information they contain—is to discover the algorithms required to perform those tasks, and to investigate their computational properties. To be sure, the physical realization of the corresponding processes in humans is a legitimate study too, but one from which the computational investigation of language may be pursued in Splendid Isolation. Complexity Theory is the mathematical study of the resources—both in time and space—required to perform computational tasks. What bounds can we place—from above or below—on the number of steps taken to compute such-and-such a function, or a function belonging to such-and-such a class? What bounds can we place on the amount of memory required? It is not surprising, therefore, that in the study of natural language, complexity-theoretic issues abound. Since any computational task can be the object of complexity-theoretic investigation, it would be hopeless even to attempt a complete survey of Complexity Theory in the study of natural language. We focus therefore on a selection of topics in natural language where there has been a particular accumulation of complexity-theoretic results. Section 2 discusses parsing and recognition; Section 3 discusses the computation of logical form; and Section 4 discusses the problem of determining logical relationships between sentences in natural language. But we begin with a brief review of the Complexity Theory itself.

It is a well-known theorem by Chomsky and Schutzenberger (1963) that every context-free language can be represented as a homomorphic image of the intersection of a Dyck language and a regular language. This paper gives a Chomsky-Schutzenberger-type characterization for multiple context-free languages, which are a natural extension of context-free languages, with introducing the notion of multiple Dyck languages, which are also a generalization of Dyck languages.

Syntactic Structures (Chomsky [6]) is widely believed to have laid the foundations of a cognitive revolution in linguistic science, and to have presented (i) the first use in linguistics of powerful new ideas regarding grammars as generative systems, (ii) a proof that English was not a regular language, (iii) decisive syntactic arguments against context-free phrase structure grammar description, and (iv) a demonstration of how transformational rules could provide a formal solution to those problems. None of these things are true. This paper offers a retrospective analysis and evaluation.

This paper examines whether the recursive structure imbedded in some exercises used in the Non Verbal Communication Device (NVCD) approach is actually the factor that enables this approach to favor language acquisition and reacquisition in the case of children with cerebral lesions. For that a definition of the principle of recursion as it is used by logicians is presented. The two opposing approaches to the problem of language development are explained. For many authors such as Chomsky [1] the faculty of language is innate. This is known as the Standard Theory; the other researchers in this field, e.g. Bates and Elman [2], claim that language is entirely constructed by the young child: they thus speak of Language Acquisition. It is also shown that in both cases, a version of the principle of recursion is relevant for human language. The NVCD approach is defined and the results obtained in the domain of language while using this approach are presented: young subjects using this approach acquire a richer language structure or re‐acquire such a structure in the case of cerebral lesions. Finally it is shown that exercises used in this framework imply the manipulation of recursive structures leading to regular grammars. It is thus hypothesized that language development could be favored using recursive structures with the young child. It could also be the case that the NVCD like exercises used with children lead to the elaboration of a regular language, as defined by Chomsky [3], which could be sufficient for language development but would not require full recursion. This double claim could reconcile Chomsky’s approach with psychological observations made by adherents of the Language Acquisition approach, if it is confirmed by researches combining the use of NVCDs, psychometric methods and the use of Neural Networks. This paper thus suggests that a research group oriented towards this problematic should be organized.

Learnability is a vital property of formal grammars: representation classes should be defined in such a way that they are learnable. One way to build learnable representations is by making them objective or empiricist: the structure of the representation should be based on the structure of the language. Rather than defining a function from representation to language we should start by defining a function from the language to the representation: following this strategy gives classes of representations that are easy to learn. We illustrate this approach with three classes, defined in analogy to the lowest three levels of the Chomsky hierarchy. First, we recall the canonical deterministic finite automaton, where the states of the automaton correspond to the right congruence classes of the language. Secondly, we define context free grammars where the non-terminals of the grammar correspond to the syntactic congruence classes, and where the productions are defined by the syntactic monoid; finally we define a residuated lattice structure from the Galois connection between strings and contexts, which we call the syntactic concept lattice, and base a representation on this, which allows us to define a class of languages that includes some non-context free languages, many context-free languages and all regular languages. All three classes are efficiently learnable under suitable learning paradigms.

SUMMARY The current work of the authors in the area of software tools for automatic construction of compilers is described. This focuses on attempts to provide for automatic production of the semantic-analysis and intermediate-code-generation parts of the Cigale compiler-writing system, developed at the University of Nice. This work relies on use of the Amsterdam Compiler Kit (ACK) to ensure a full set of optimizers and code generators based on a semi-universal intermediate language, and, therefore, emphasizes the filling of the gap between parsing and the intermediate language. It is intended as a pragmatic contribution to the automation of the production of true compilers (rather than mere program evaluators) that generate efficient machine code.

A new language system, the AUTOMATED PROGRAMMER, has been designed and implemented. It aims to automate a great deal of routine effort for scientific, engineering, and mathematical application programming. Its notation is modeled after conventional textbook mathematical representation so that mathematical expressions may be entered just as they appear in conventional solution specifications. It employs a flexible vocabulary and syntax that emulates technical English. This approach enhances self-documentation, diminishes programming error, and eases maintainability and verifiability. System design is highly user-oriented so as to make the system easy to learn and use. Programs are input via a two-dimensional screen editor using a four-case English, Greek, and mathematical symbol alphabet. Lexical restrictions are minimal, keyword synonyms are available, and various common synonymous syntactic structures, mimicking technical English, are acceptable. Matrix arithmetic is accomplished using standard textbook notation. Powerful input and output facilities are provided.

Exploratory language design is an iterative process of language refinement the purpose of which is to define a language that closely fits a given domain of applications. First, choose a domain of applications and a language starting point. Then iteratively choose an application in the domain, write the solution to the application in the language, and fit the language to the application until satisfied.

Introduction In this chapter, the argument will take a somewhat different tack. Up to now, it has been the general theoretical themes of the MP that have been under attack from an evolutionary standpoint. In chapter 5, the specifics of minimalist syntactic theories will be examined in a similar light. Before that, this chapter will put one evolutionary hypothesis, which is clearly consonant with minimalist thinking, under the spotlight. Hauser et al . (2002) propose that the core component underlying language is recursion, and that all other intricacies and peculiarities of our linguistic capacity are the result of the recursive component having to interface with systems of the brain which are external to language, but are called upon in the course of processing language. As the one property which permits human language to be given the label of unique , what is interesting from an evolutionary view is the emergence of recursion. It is important to take heed of the authors' disclaimer. They do not ‘define FLN as recursion by theoretical fiat’ (Fitch et al . 2005: 183). Indeed, in places, they appear to retreat to a weaker position. However, as they also note, ‘[t]he contents of FLN are to be empirically determined’ (p. 182). That is, the recursion-only hypothesis is just that, a hypothesis about the nature of language and its evolution, and the only way to prove or disprove it is to examine the empirical data. That is precisely what this chapter will do – use the empirical data to assess the hypothesis that ‘FLN only includes recursion’ (Hauser et al . 2002: 1569). Section 4.2 will examine in detail what the term recursion refers to.

Classifications of the functions of language reflect the interests and goals of the one classifying. Most utterances serve more than one function, and communication includes more than transferring information. Speech act taxonomies highlight illocutionary acts, for example, constatives, directives, commissives, and acknowledgments. Other taxonomies, such as Halliday's, divide functions into referential-informational, interpersonal, and textual. Jacobson's system adds aesthetic and phatic functions. Phatic communion, a term from Malinowski, serves to create social bonds.

International audience; Functional graph grammars are finite devices which generate the class of regular automata. We recall the notion of synchronization by grammars, and for any given grammar we consider the class of languages recognized by automata generated by all its synchronized grammars. The synchronization is an automaton-related notion: all grammars generating the same automaton synchronize the same languages. When the synchronizing automaton is unambiguous, the class of its synchronized languages forms an effective boolean algebra lying between the classes of regular languages and unambiguous context-free languages. We additionally provide sufficient conditions for such classes to be closed under concatenation and its iteration.

A regular language is called union-free if it can be represented by a regular expression that does not contain the union operation. Every regular language can be represented as a finite union of union-free languages (the so-called union-free decomposition ), but such decomposition is not necessarily unique. We call the number of components in the minimal union-free decomposition of a regular language the union width of the regular language. In this paper we prove that the union width of any regular language can be effectively computed and we present an algorithm for constructing a corresponding decomposition. We also study some properties of union-free languages and introduce a new algorithm for checking whether a regular language is union-free.

We propose to model the development of language by a series of formal grammars, accounting for the linguistic capacity of children at the very early stages of mastering language. This approach provides a testbed for evaluating theories of language acquisition, in particular with respect to the extent to which innate, language-specific mechanisms must be assumed. Specifically, we focus on a single child learning English and use the CHILDES corpus for actual performance data. We describe a set of grammars which account for this child's utterances between the ages 1;8.02 and 2;0.30. The coverage of the grammars is carefully evaluated by extracting grammatical relations from induced structures and comparing them with manually annotated labels.

We prove that every regular language is recognized by a deterministic two-way finite automaton whose control unit is strictly locally testing. Similarly, every picture language which can be described by a regular language can actually be described by a strictly locally testable language; this strengthens a result of Friedhelra Hinz.

We investigate the relative expressive power of finite delay operators in SCCS. These were introduced by Milner and by Hennessy to study fairness properties of processes in the context of SCCS. We show that the context sensitive delay operator introduced by Hennessy is more expressive than the finite delay operator introduced by Milner. This result is closely related to recent results by Panangaden and Stark on the expressive power of fair merge in asynchronous dataflow (Kahn) networks. It indicates that the expressiveness results obtained there are not sensitive to the precise computational model since SCCS, unlike Kahn networks, is synchronous and permits expansion of recursively defined processes.

Membrane computing is a branch of natural computing which abstracts computing models from the structure and the functioning of the living cell. The main ingredients of membrane systems, called P systems, are (i) the membrane structure, which consists of a hierarchical arrangements of membranes which delimit compartments where (ii) multisets of symbols, called objects, evolve according to (iii) sets of rules which are localised and associated with compartments. By using the rules in a nondeterministic/deterministic maximally parallel manner, transitions between the system configurations can be obtained. A sequence of transitions is a computation of how the system is evolving. Various ways of controlling the transfer of objects from one membrane to another and applying the rules, as well as possibilities to dissolve, divide or create membranes have been studied. Membrane systems have a great potential for implementing massively concurrent systems in an efficient way that would allow us to solve currently intractable problems once future biotechnology gives way to a practical bio-realization. In this paper we survey some interesting and fundamental complexity issues such as universality vs. nonuniversality, determinism vs. nondeterminism, membrane and alphabet size hierarchies, characterizations of context-sensitive languages and other language classes and various notions of parallelism.

This paper concerns methods to check for atomic-set serializability violations in concurrent Java programs. The straightforward way to encode a reentrant lock is to model it with a context-free language to track the number of successive lock acquisitions. We present a construction that replaces the context-free language that describes a reentrant lock by a regular language that describes a non-reentrant lock. We call this replacement language strength reduction. Language strength reduction produces an average speedup (geometric mean) of 3.4. Moreover, for 2 programs that previously exhausted available space, the tool is now able to run to completion.

The algebraic approach to formal language and automata theory is a continuation of the earliest traditions in these fields which had sought to represent languages, translations and other computations as expressions (e.g. regular expressions) in suitably-defined algebras; and grammars, automata and transitions as relational and equational systems over these algebras, that have such expressions as their solutions. The possibility of a comprehensive foundation cast in this form, following such results as the algebraic reformulation of the Parikh Theorem, has been recognized by the Applications of Kleene Algebra (AKA) conference from the time of its inception in 2001. Here, we take another step in this direction by embodying the Chomsky hierarchy, itself, within an infinite complete lattice of algebras that ranges from dioids to quantales, and includes many of the forms of Kleene algebras that have been considered in the literature. A notable feature of this development is the generalization of the Chomsky hierarchy, including type 1 languages, to arbitrary monoids.

In this paper we have developed a context sensitive translator for optically recognizing the Braille codes for Urdu language. Urdu is a context sensitive language and have different glyphs of an alphabet depending upon the position of use. Our research is aimed at bridging the gap between blind and sighted people. We developed Braille codes for Urdu, scanned the Braille, recognized it optically, devised a deterministic Turing machine for context sensitive translation and generated the output in Urdu.

The use of formal designs of languages as language definitions is described. From such definitions more typical language definitions can be derived. Also, unlike typical language definitions, formal designs can easily be manipulated into designs for other languages for the same underlying domain. Unlike the traditional definition of a language given as a syntax and semantics, a definition by abstract design in invertible , meaning that one can use it to map evaluated meanings to terms in the language, as well as for the more usual task of mapping terms in the language to evaluated meanings.

We present a language for acyclic chemical groups, which has a context-free grammar, and which is close to current chemical denotations. An interpreter which accepts the language, produces a connection table, and performs valency checks has been written in PASCAL. The source code and executable program are included on disk.

Classical Context Sensitive languages can be parsed by dynamically adding or removing production rules from the rules set. The grammar is modified according to the context, and evolves during parsing, allowing to take the context into consideration at the syntactical level and not in a separate semantic analysis. This approach has proven greater flexibility in the definition of programming languages, improving the readability and maintenability of program codes and the general usability of the language, thus improving the human-computer interaction. Examples of implementation of classical context sensitive languages as well as examples derived from practical applications are provided.