Targets-Drives-Means: A declarative approach to dynamic behavior specification with higher usability

Small humanoid robots are becoming more affordable and are now used in fields such as human–robot interaction, ethics, psychology, or education. For non-roboticists, the standard paradigm for robot visual programming is based on the selection of behavioral blocks, followed by their connection using communication links. These programs provide efficient user support during the development of complex series of movements and sequential behaviors. However, implementing dynamic control remains challenging because the data flow between components to enforce control loops, object permanence, the memories of object positions, odometry, and finite state machines has to be organized by the users. In this study, we develop a new programming paradigm, Targets-Drives-Means, which is suitable for the specification of dynamic robotic tasks. In this proposed approach, programming is based on the declarative association of reusable dynamic components. A central memory organizes the information flows automatically and issues related to dynamic control are solved by processes that remain hidden from the end users. The proposed approach has advantages during the implementation of dynamic behaviors, but it requires that users stop conceiving robotic tasks as the execution of a sequence of actions. Instead, users are required to organize their programs as collections of behaviors that run in parallel and compete for activation. This might be considered non-intuitive but we also report the positive outcomes of a usability experiment, which evaluated the accessibility of the proposed approach.     

An approach to information requirements specification for process control tasks

This paper discusses the need for designers of process plant supervisory systems to make greater effort in anticipating the information that operators require to carry out their duties. A method for dealing with this problem of information requirements specification in process plant design is proposed. This method translates a task analysis into a set of standard task elements from which standard sets of information, called ‘sub-goal templates’ can be derived. The resultant information requirements specification sets out the operators' information needs in the context of the operating goals that have to be attained. Early trials with the method indicate its promise, but highlight the need for its implementation in a computer tool to assist the designer. The features of such a tool and the further work necessary to develop and test the method are described.     

SelfMotion: A declarative approach for adaptive service-oriented mobile applications

Modern society increasingly relies on mobile devices. This explains the growing demand for high quality software for such devices. To improve the efficiency of the development life-cycle, shortening time-to-market while keeping quality under control, mobile applications are typically developed by composing together ad-hoc developed components, services available on-line, and other third-party mobile applications. Applications are thus built as heterogeneous compositions, whose characteristics strongly depend on the components and services they integrate. To cope with unpredictable changes and failures, but also with the various settings offered by the plethora of available devices, mobile applications need to be as adaptive as possible. However, mainstream adaptation strategies are usually defined imperatively and require complex control strategies strongly intertwined with the application logic, yielding to applications that are difficult to build, maintain, and evolve. We address this issue by proposing a declarative approach to compose adaptive heterogeneous mobile applications. The advantages of this approach are demonstrated through an example inspired by an existing worldwide distributed mobile application, while the implementation of the proposed solution has been validated through a set of simulations and experiments aimed at illustrating its performance.     

面向半物理仿真的陈述式模型求解方法研究

通过符号操作和数值计算相结合,提出了一种求解半物理仿真模型的新方法。为了满足半物理仿真对实时性的要求,在模型编译阶段将代表数值积分的隐式离散公式插入到仿真模型中,增广后的方程系统伴随着非线性方程的出现,需要在积分的每一步对这些非线性方程进行迭代求解,而求解非线性方程的时间复杂度随维度的变大成指数增加,因此引入代数环撕裂减小代数方程块耦合变量数,以满足实时求解对粒度的要求。最后通过实例对文中提出的方法进行了验证。     

A syntax-directed parser for recalcitrant grammars

This paper deals with a syntax-directed parsing scheme being used in a PL/I compiler for the CDC 6600. It uses a highly restricted grammar of the class LL(1) for efficiency, with an escape hatch for those cases excluded by the grammar. These cases are handled by oracles that can make decisions without a full-scale syntactic analysis. The input to SYNDIPAR, the SYNtax Directed PARser, consists of syntax equations, semantic routines, and token class definitions; the output consists of a PARSE procedure in PL/I together with certain tables. The PARSE procedure works in conjunction with a lexical scanner, designed to allow look-ahead by oracles in a uniform fashion. The actual parsing process takes place through the interpretation of a program compiled by SYNDIPAR for a parsing machine. The instruction set of the parsing machine is described, and an example of the compilation of a syntax equation is given.     

A declarative approach to visualizing concurrent computations

The authors explore the graphical representation of objects and processes as a means for understanding programs consisting of large numbers of concurrent processes. Their goal is to establish a technical foundation for research into the monitoring and debugging of large-scale concurrent programs. They explain declarative visualization and introduce some shared-data-space concepts and notation by means of a simple, nondeterministic, parallel algorithm. They discuss visual abstraction and their visualization methodology, which they illustrate by applying it to region labeling. Thy examine the relaxation of nonintervention that visualization makes possible     

XChange: A semantic diff approach for XML documents

XML documents are extensively used in several applications and evolve over time. Identifying the semantics of these changes becomes a fundamental process to understand their evolution. Existing approaches related to understanding changes (diff) in XML documents focus only on syntactic changes. These approaches compare XML documents based on their structure, without considering the associated semantics. However, for large XML documents, which have undergone many changes from a version to the next, a large number of syntactic changes in the document may correspond to fewer semantic changes, which are then easier to analyze and understand. For instance, increasing the annual salary and the gross pay, and changing the job title of an employee (three syntactic changes) may mean that this employee was promoted (one semantic change). In this paper, we explore this idea and present the XChange approach. XChange considers the semantics of the changes to calculate the diff of different versions of XML documents. For such, our approach analyzes the granular syntactic changes in XML attributes and elements using inference rules to combine them into semantic changes. Thus, differently from existing approaches, XChange proposes the use of syntactic changes in versions of an XML document to infer the real reason for the change and support the process of semantic diff. Results of an experimental study indicate that XChange can provide higher effectiveness and efficiency when used to understand changes between versions of XML documents when compared with the (syntactic) state-of-the-art approaches.     

A grammatical approach to self-organizing robotic systems

In this paper, we define a class of graph grammars that can be used to model and direct concurrent robotic self-assembly and similar self-organizing processes. We give several detailed examples of the formalism and then focus on the problem of synthesizing a grammar so that it generates a given, prespecified assembly. In particular, to generate an acyclic graph we synthesize a binary grammar (rules involve at most two parts), and for a general graph we synthesize a ternary grammar (rules involve at most three parts). In both cases, we characterize the number of concurrent steps required to achieve the assembly. We also show a general result that implies that no binary grammar can generate a unique stable assembly. We conclude the paper with a discussion of how graph grammars can be used to direct the self-assembly of robotic parts.     

A grammatical optimization approach for integrated process planning and scheduling

Rapid developments in computerized manufacturing environments and increasing overlapping in the capability of manufacturing resources provoked integration of many manufacturing functions including process planning scheduling. Several approaches have been developed in the literature in order to integrate process planning and scheduling. In this paper a novel approach which makes use of grammatical representation of generic process plans is used within a multiple objective tabu search framework in order to integrate process planning and scheduling effectively. Detailed explanations along with an example problem are presented in the paper. Proposed approach is tested on literature problems and also hypothetically generated flexible job shop scheduling problems with alternative process plans to analyze its performance and efficiency.     

Automaton meets algebra: A hybrid paradigm for XML stream processing

XML stream applications bring the challenge of efficiently processing queries on sequentially accessible token-based data streams. The automata paradigm is naturally suited for pattern recognition on tokenized XML streams, but requires patches for fulfilling the filtering or restructuring functionalities in the XML query language. In contrast, the algebraic paradigm is a well-established technique for processing self-contained tuples. It however does not traditionally support token inputs. The Raindrop framework is the first to accommodate these two paradigms within one algebraic framework, taking advantage of both. This paper describes the overall framework, highlighting in particular three aspects. First, we describe how the tokens and tuples are modeled in one uniform query processing model. Second, we present the query rewriting that switches computations between these two data models. Third, we discuss strategies for the implementation and synchronization of the operators within the framework. We report experimental results that illustrate the unique optimization opportunities offered by this novel framework.     

A specification language for the processing of technical-economic indicators

The paper describes a specification language for the processing of records with technical—economic content in distributed control systems. The principles of the specification language are close to logic languages and to data-structure oriented languages. The language has been implemented on a computer system.Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 152–164, 179, July–august, 1991.     

Automaton meets algebra: A hybrid paradigm for XML stream processing

XML stream applications bring the challenge of efficiently processing queries on sequentially accessible token-based data streams. The automata paradigm is naturally suited for pattern recognition on tokenized XML streams, but requires patches for fulfilling the filtering or restructuring functionalities in the XML query language. In contrast, the algebraic paradigm is a well-established technique for processing self-contained tuples. It however does not traditionally support token inputs. The Raindrop framework is the first to accommodate these two paradigms within one algebraic framework, taking advantage of both. This paper describes the overall framework, highlighting in particular three aspects. First, we describe how the tokens and tuples are modeled in one uniform query processing model. Second, we present the query rewriting that switches computations between these two data models. Third, we discuss strategies for the implementation and synchronization of the operators within the framework. We report experimental results that illustrate the unique optimization opportunities offered by this novel framework.     

A metamodeling approach for pattern specification and management

The formal specification of design patterns is central to pattern research and is the foundation of solving various pattern-related problems.In this paper,we propose a metamodeling approach for pattern specification,in which a pattern is modeled as a meta-level class and its participants are meta-level references.Instead of defining a new metamodel,we reuse the Unified Modeling Language(UML)metamodel and incorporate the concepts of Variable and Set into our approach,which are unavailable in the UML but essential for pattern specification.Our approach provides straightforward solutions for pattern-related problems,such as pattern instantiation,evolution,and implementation.By integrating the solutions into a single framework,we can construct a pattern management system,in which patterns can be instantiated,evolved,and implemented in a correct and manageable way.     

An efficient XML encoding and labeling method for query processing and updating on dynamic XML data

In this paper, we propose an efficient encoding and labeling scheme for XML, called EXEL, which is a variant of the region labeling scheme using ordinal and insert-friendly bit strings. We devise a binary encoding method to generate the ordinal bit strings, and an algorithm to make a new bit string inserted between bit strings without any influences on the order of preexisting bit strings. These binary encoding method and bit string insertion algorithm are the bases of the efficient query processing and the complete avoidance of re-labeling for updates. We present query processing and update processing methods based on EXEL. In addition, the Stack-Tree-Desc algorithm is used for an efficient structural join, and the String B-tree indexing is utilized to improve the join performance. Finally, the experimental results show that EXEL enables complete avoidance of re-labeling for updates while providing fairly reasonable query processing performance.     

A declarative approach to procedural modeling of virtual worlds

With the ever increasing costs of manual content creation for virtual worlds, the potential of creating it automatically becomes too attractive to ignore. However, for most designers, traditional procedural content generation methods are complex and unintuitive to use, hard to control, and generated results are not easily integrated into a complete and consistent virtual world.We introduce a novel declarative modeling approach that enables designers to concentrate on stating what they want to create instead of on describing how they should model it. It aims at reducing the complexity of virtual world modeling by combining the strengths of semantics-based modeling with manual and procedural approaches. This article describes two of its main contributions to procedural modeling of virtual worlds: interactive procedural sketching and virtual world consistency maintenance. We discuss how these techniques, integrated in our modeling framework SketchaWorld, build up to enable designers to create a complete 3D virtual world in minutes. Procedural sketching provides a fast and more intuitive way to model virtual worlds, by letting designers interactively sketch their virtual world using high-level terrain features, which are then procedurally expanded using a variety of integrated procedural methods. Consistency maintenance guarantees that the semantics of all terrain features is preserved throughout the modeling process. In particular, it automatically solves conflicts possibly emerging from interactions between terrain features.We believe that these contributions together represent a significant step towards providing more user control and flexibility in procedural modeling of virtual worlds. It can therefore be expected that by further reducing its complexity, virtual world modeling will become accessible to an increasingly broad group of users.     

基于列表的可扩展标记语言流数据查询处理方法

针对半结构化可扩展标记语言(XML)流数据实时在线到达,顺序性一次访问及处理时效性高、缓存量小的需求,以及目前算法在大规模数据处理中查询表达式的能力有限、效率尚不能满足实际应用的现状,基于SAX解析,提出以列表及关系指针组合处理XPath查询的QXSList方法。首先定义数据模型,给出算法实现的整体框架,然后分别针对两个不同的XPath查询片段重点考虑了谓词判断条件和通配符的处理方法;该方法通过层次值计算判断节点的结构关系,利用关系指针链接多个候选节点列表,获取查询查询结果;最后分析给出优化算法,进一步减少缓存管理。通过实验对该方法与QStream++方法及MonetDB和SAXON查询引擎的运行时间和内存占比进行分析,得出与同类算法相比,随着数据量级的增加,效率提升在30%以上,且运行过程中内存占比接近于常量。     

Algebraic specification of data types: A synthetic approach

A mathematical interpretation is given to the notion of a data type, which allows procedural data types and circularly defined data types. This interpretation seems to provide a good model for what most computer scientists would call data types, data structures, types, modes, clusters or classes. The spirit of this paper is that of McCarthy [43] and Hoare [18]. The mathematical treatment is the conjunction of the ideas of Scott on the solution of domain equations [34], [35], and [36] and the initiality property noticed by the ADJ group (ADJ [2] and [3]). The present work adds operations to the data types proposed by Scott and proposes an alternative to the equational specifications proposed by Guttag [14], Guttag and Horning [15] and ADJ [2]. The advantages of such a mathematical interpretation are the following: throwing light on some ill-understood constructs in high-level programming languages, easing the task of writing correct programs and making possible proofs of correctness for programs or implementations.This research was conducted at the University of Warwick while both authors were supported by the Science Research Council grant B/RG 31948 to D. Park and M. Paterson. During the final redaction of the paper the first author was partially supported by the National Science Foundation grant MCS78-07461. EDITOR'S NOTE: This paper is one of several invited for submission to this journal to present different approaches to the subject of the semantics of programming languages.     

SOFSPEC: A pragmatic approach to automated specification verification

This paper describes a system for the automatic verification of commerical application specifications—SOFSPEC. After having established a relationship to the other requirement specification approaches, the user interface and the database schema are presented. The database schema is based on the entity/relationship model and encompasses four entities and six relationships with a varying number of attributes. These are briefly outlined. Then, the paper describes how these entities and relations are checked against one another in order to ascertain the completeness and consistency of the specification before it is finally documented.