逐步求精法获取上下文无关文法

文法推断研究如何从语言的有限实例,通过归纳推断获取语言的文法定义。文中提出一个基于逐步求精的上下文无关文法推断方法,以尝试将文法推断用于替代或帮助传统手工的文法构造工作。文中的推断方法以Ａｎｇｌｕｉｎｈ的交互式学习模型为框架,以逐步求精和复用为主要策略,具有增量式获取结构自然的文法的特点。     

Self-organization of Decentralized Swarm Agents Based on Modified Particle Swarm Algorithm

In this paper, an attempt has been made by incorporating some special features in the conventional particle swarm optimization (PSO) technique for decentralized swarm agents. The modified particle swarm algorithm (MPSA) for the self-organization of decentralized swarm agents is proposed and studied. In the MPSA, the update rule of the best agent in swarm is based on a proportional control concept and the objective value of each agent is evaluated on-line. In this scheme, each agent self-organizes to flock to the best agent in swarm and migrate to a moving target while avoiding collision between the agent and the nearest obstacle/agent. To analyze the dynamics of the MPSA, stability analysis is carried out on the basis of the eigenvalue analysis for the time-varying discrete system. Moreover, a guideline about how to tune the MPSA's parameters is proposed. The simulation results have shown that the proposed scheme effectively constructs a self-organized swarm system in the capability of flocking and migration.Category (5) – Intelligent Systems / Intelligent Control / Fuzzy Control / Prosthetics / Robot Motion Planning     

Chinese lattice designs and parametric shape grammars

Chinese lattice designs are a rich source of interesting geometric forms. We describe a parametric shape grammar that generates ice-ray lattices. We also provide an overview of shape grammars — formal, graphical production systems that perform graphical computations with parametric labeled shapes (finite arrangements of nonzero line segments with a finite set of labeled points).     

Generalised Stream X-Machines and Cooperating Distributed Grammar Systems

Stream X-machines are a general and powerful computational model. By coupling the control structure of a stream X-machine with a set of formal grammars a new machine called a generalised stream X-machine with underlying distributed grammars, acting as a translator, is obtained. By introducing this new mechanism a hierarchy of computational models is provided. If the grammars are of a particular class, say regular or context-free, then finite sets are translated into finite sets, when ?k, = k derivation strategies are used, and regular or context-free sets, respectively, are obtained for ?k, * and terminal derivation strategies. In both cases, regular or context-free grammars, the regular sets are translated into non-context-free languages. Moreover, any language accepted by a Turing machine may be written as a translation of a regular set performed by a generalised stream X-machine with underlying distributed grammars based on context-free rules, under = k derivation strategy. On the other hand the languages generated by some classes of cooperating distributed grammar systems may be obtained as images of regular sets through some X-machines with underlying distributed grammars. Other relations of the families of languages computed by generalised stream X-machines with the families of languages generated by cooperating distributed grammar systems are established. At the end, an example dealing with the specification of a scanner system illustrates the use of the introduced mechanism as a formal specification model. Received September 1999 / Accepted in revised form October 2000     

Parallel communicating grammar systems with terminal transmission

We introduce a new variant of PC grammar systems, called PC grammar systems with terminal transmission, PCGSTT for short. We show that right-linear centralized PCGSTT have nice formal language theoretic properties: they are closed under gsm mappings (in particular, under intersection with regular sets and under homomorphisms) and union; a slight variant is, in addition, closed under concatenation and star; their power lies between that of n-parallel grammars introduced by Wood and that of matrix languages of index n, and their relation to equal matrix grammars of degree n is discussed. We show that membership for these language classes is complete for NL. In a second part of the paper, we discuss questions concerning grammatical inference of these systems. More precisely, we show that PCGSTT whose component grammars are terminal distinguishable right-linear, a notion introduced by Radhakrishnan and Nagaraja in [33,34], are identifiable in the limit if certain data communication information is supplied in addition.     

Cooperating/distributed grammar systems with hypothesis languages

Abstract

Motivated by the blackboard model of artificial intelligence we introduce the concept of context-free cooperating/distributed grammar systems with hypothesis languages. We prove that these grammar systems have the same generative power as context-sensitive grammars.     

Swarm aggregations of heterogeneous multi-agent systems

This paper investigates the problem of swarm aggregations of heterogeneous multi-agent systems. Comparing with the existing studies on swarm aggregations of homogeneous multi-agent systems, this paper is much more resembling the practical situations, where the agents have different dynamics. We show that the heterogeneous agents will gather with a certain error under some assumptions and conditions. The stability properties have been proven by theoretical analysis and verified via numerical simulation. The stability of the heterogeneous multi-agent systems has been achieved based on matrix theory and the Lyapunov stability theorem. Numerical simulation is given to demonstrate the effectiveness of the theoretical result.     

Context-free like restrictions on selective rewriting

Selective substitution grammars based on ‘context-free’ productions form a possible framework for the study of ‘grammatically oriented’ formal language theory. Such grammars (with no control governing the composition of derivation steps) are studied in this paper. In particular we study the effect of various conditions on selectors (which define the way that rewriting is performed); those conditions are aimed to formalize the notion of ‘using information about the context’ during the rewriting process. Each of them captures a particular feature of a rewriting according to a context-free grammar or an EOS system (essentially a context-free grammar that can also rewrite terminal symbols). Some of those conditions yield characterizations of the class of context-free languages for other conditions the lower and upper bound on the language generating power are given. Also a natural notion of a class of ‘simple’ rewriting systems is introduced (pattern grammars) and it is demonstrated that they possess surprisingly high language generating power.     

vCGG:一种基于虚结点的空间图文法形式框架

作为一种二维的形式化方法,图文法为可视化语言提供了直观而规范的描述手段.然而,大多数图文法形式框架在空间语义处理能力方面有所不足,影响了图文法的表达能力及其实际应用范围.针对现存的问题,构建了一种新型空间图文法形式框架vCGG （virtual-node based coordinate graph grammar）.区别于其他空间图文法,vCGG在产生式中通过定义虚结点的概念描述产生式与主图之间的语法结构与空间语义关系,在保留抽象能力的同时,提高了其空间语义配置性能.通过与几种典型空间图文法框架比较,vCGG形式框架在直观性、规范性、表达能力以及分析效率方面均有着较好的表现.     

L-fuzzy grammars

An L-fuzzy grammar is defined by assigning the element of lattice to the rewriting rules of a formal grammar. According to the kind of lattice, say, distributive lattice, lattice-ordered group, and lattice-ordered monoid, two type of L-fuzzy grammars are defined. It is shown that some context-sensitive languages can be generated by type 3 $\text{1-L-}\text{fuzzy}$ grammars with cut points. It is also shown that for type 2 L-fuzzy grammars, Chomsky and Greibach normal form can be constructed as an extension of corresponding notion in the theory of formal grammars.     

Distinguishing redundant parentheses by syntax

We give a generalized formal schema for designing a context free expression grammar that distinguishes required parentheses from redundant parentheses by means of formal syntax alone. The method applies to expression grammars having binary operators at any number of precedence levels, each level having any number of operators and being either left-associative, right-associative, or (syntactically) non-associative. We give proofs of correct parsing, unambiguity, LR(1)-ness, and the distinction of redundant parentheses. The resulting grammars appear to be LALR(1).     

Formalized analysis of structural characteristics of large complexsystems

Macrostructural modelization is paramount to the development of large complex systems (LCS). The paper explores the macrostructural modelization of LCS in terms of a block diagram based model and a grammar based model. Firstly, the macrostructural modelization problem of LCS is formulated. Secondly, a block diagram based model is proposed and established for LCS. Specifically, two general-purpose information-processing modules are proposed and constructed, called perception cube and decision spheroid. Thirdly, a grammar based model is proposed and established for LCS through applying formal language theory to the block diagram based model. Specifically, perception cube and decision spheroid are visually represented as context-free grammars, named fusion grammar and synthesis grammar, respectively. Through a stratified constructive linkup between a stream of bottom-up growing fusion grammars and a stream of top-down growing synthesis grammars, a level of LCS is constructively defined and accordingly represented as a context-free grammar, named level grammar. Then, a whole LCS is represented as a context-free grammar through a compounding of all level grammars. Finally, a case study is presented to demonstrate the potential usability of the proposed and established models of LCS     

A formal methodology using attributed grammars for multiprocessing-system software development. I. Design representation

With the growing complexity of multiprocessing systems and distributed computing systems, there is an increasing need to provide a formal methodology for deriving a model to represent software design for the software development of these systems. The formal methodology presented in this paper uses attributed grammars, and extends formal methods commonly used in the definition of programming languages and compiler techniques for representing the design specification of software systems and validating the implementation. This model provides a common basis in the software development phases through automated design analysis, test-case generation, and validation of the software system. This paper covers the construction of the model for the design representation using attributed grammar and the analysis of the software system design based on the model.     

Modeling and stability analysis of social foraging swarms in multi-obstacle environment

In this article we specify an individual-based foraging swarm (i.e., group of agents) model with individuals that move in an n-dimensional multi-obstacle environment. The motion of each individual (i) is determined by three factors: i) attraction to the local object position (xˉio+ ) which is decided by the local information about the individuals’ position that individual i can find; ii) repulsion from the other individuals on short distances; and iii) attraction to the global object position (xgoal ) or repulsion from the obstacles in the environment. The emergent behavior of the swarm motion is the result of a balance between inter-individual interaction and the simultaneous interactions of the swarm members with their environment. We study the stability properties of the collective behavior of the swarm based on Lyapunov stability theory. The simulations show that the swarm can converge to goal regions and diverge from obstacle regions of the environment while maintaining cohesive.     

AN UNSUPERVISED INCREMENTAL LEARNING ALGORITHM FOR DOMAIN-SPECIFIC LANGUAGE DEVELOPMENT

While grammar inference (or grammar induction) has found extensive application in the areas of robotics, computational biology, and speech recognition, its application to problems in programming language and software engineering domains has been limited. We have found a new application area for grammar inference which intends to make domain-specific language development easier for domain experts not well versed in programming language design, and finds a second application in construction of renovation tools for legacy software systems. As a continuation of our previous efforts to infer context-free grammars (CFGs) for domain-specific languages which previously involved a genetic-programming based CFG inference system, we discuss extensions to the inference capabilities of GenInc, an incremental learning algorithm for inferring CFGs. We show that these extensions enable GenInc to infer more comprehensive grammars, discuss the results of applying GenInc to various domain-specific languages and evaluate the results using a comprehensive suite of grammar metrics.     

Coordination and communication issues in multi-agent expert system: concurrent configuration design advisor

The model of concurrent configuration design and the architecture of Concurrent Configuration Design Advisor (CCDA) are considered. The CCDA is developed as an open dynamic expert system of interacting agents. In the context of this article a configuration problem is defined as a decision-making procedure performed by concurrent processes (agents). The analysis of concurrent and sequential activities in this system is based on structural transformations (in the form of graph grammars) that permits the definition of correct criteria for data integrity and the consistency of configured project data model, and any dynamic changes in the project to be modeled conveniently. This approach also makes it possible to handle complex hierarchial data structures of real configured objects and to model communication and synchronization of decision making in a distributed expert system in a common formalism. The system to be configured is decomposed into structured objects, called fragments. The proposed model consists of three types of agents. D-agents are those capable of the object configuration design within the constraints on their attributes. To cope with agents' coordination, objects' consistency and data integrity problems, a special type of agent, facilitator or F-agent, is introduced. Finally, project assistants or A-agents are responsible for the user interface at the stage of object model definition. The discussion is illustrated with examples from the application domain of flexible manufacturing systems. Experimental results, current and future work on the expert system implementation are considered.     

Decentralized Control of Autonomous Swarm Systems Using Artificial Potential Functions: Analytical Design Guidelines

This paper presents a framework for decentralized control of self-organizing swarm systems based on the artificial potential functions (APFs). In this scheme, multiple agents in a swarm self-organize to flock and achieve formation control through attractive and repulsive forces among themselves using APFs. In particular, this paper presents a set of analytical guidelines for designing potential functions to avoid local minima for a number of representative scenarios. Specifically the following cases are addressed: 1) A non-reachable goal problem (a case that the potential of the goal is overwhelmed by the potential of an obstacle, 2) an obstacle collision problem (a case that the potential of the obstacle is overwhelmed by the potential of the goal), 3) an obstacle collision problem in swarm (a case that the potential of the obstacle is overwhelmed by potential of other robots in a group formation) and 4) an inter-robot collision problem (a case that the potential of the robot in a formation is overwhelmed by potential of the goal). The simulation results showed that the proposed scheme can effectively construct a self-organized swarm system with the capability of group formation, navigation and migration in the presence of obstacles.Category (5) – Intelligent Systems/Intelligent Control/Fuzzy Control/Prosthetics/Robot Motion Planning     

The formal power of one-visit attribute grammars

Summary An attribute grammar is one-visit if the attributes can be evaluated by walking through the derivation tree in such a way that each subtree is visited at most once. One-visit (1V) attribute grammars are compared with one-pass left-to-right (L) attribute grammars and with attribute grammars having only one synthesized attribute (1S).Every 1S attribute grammar can be made one-visit. One-visit attribute grammars are simply permutations of L attribute grammars; thus the classes of output sets of 1V and L attribute grammars coincide, and similarly for 1S and L-1S attribute grammars. In case all attribute values are trees, the translation realized by a 1V attribute grammar is the composition of the translation realized by a 1S attribute grammar with a deterministic top-down tree transduction, and vice versa; thus, using a result of Duske e.a., the class of output languages of 1V (or L) attribute grammars is the image of the class of IO macro tree languages under all deterministic top-down tree transductions.     

基于属性文法和语义网络的综合知识表示模型

本文提出了一个属性文法计算模型与语义网络表示模型相结合的综合知识表示模型.根据形式化的语义网络表示模型和属性文法的特点,该模型使用属性文法的符号建立了一些适合于语义网络表示模型的语法和语义规则模式,并且可通过扩充的属性文法的解释器来实现推理.