Context-free graph grammars and concatenation of graphs

An operation of concatenation is defined for graphs. This allows strings to be viewed as expressions denoting graphs, and string languages to be interpreted as graph languages. For a class of string languages, is the class of all graph languages that are interpretations of languages from . For the classes REG and LIN of regular and linear context-free languages, respectively, . is the smallest class of graph languages containing all singletons and closed under union, concatenation and star (of graph languages). equals the class of graph languages generated by linear HR (= Hyperedge Replacement) grammars, and is generated by the corresponding -controlled grammars. Two characterizations are given of the largest class such that . For the class CF of context-free languages, lies properly inbetween and the class of graph languages generated by HR grammars. The concatenation operation on graphs combines nicely with the sum operation on graphs. The class of context-free (or equational) graph languages, with respect to these two operations, is the class of graph languages generated by HR grammars. Received 16 October 1995 / 18 September 1996     

Networks of evolutionary processors: the power of subregular filters

In this paper, we propose a hierarchy of families of languages generated by networks of evolutionary processors where the filters belong to several special classes of regular sets. More precisely, we show that the use of filters from the class of ordered, non-counting, power-separating, circular, suffix-closed regular, union-free, definite, and combinational languages is as powerful as the use of arbitrary regular languages and yields networks that can generate all the recursively enumerable languages. On the other hand, the use of filters that are only finite languages allows only the generation of regular languages, but not every regular language can be generated. If we use filters that are monoids, nilpotent languages, or commutative regular languages, we obtain one and the same family of languages which contains non-context-free languages but not all regular languages. These results seem to be of interest because they provide both upper and lower bounds on the families of languages that one can use as filters in a network of evolutionary processors in order to obtain a complete computational model.     

Characterizations of regular and context-free matrices

The u-v theorem for context-free languages is extended to prove an intercalation theorem for the family of context-free matrix languages. A row-wise iteration factor theorem is proved for the families of regular and context-free matrix languages. Characterizations of regular and context-free matrix languages are given in terms of vertical regular sequences and simple operations on vertical regular sequences. Closure of regular and context-free matrix languages under array nondeterministic finite state transducer mappings is established and an image theorem proved. This is used to give another characterization of regular matrix languages. Further it is shown that the family of regular matrix languages is a principal abstract family of matrices (AFM). The effect of string control and array control on these families are examined.     

Accepting Networks of Evolutionary Processors with Subregular Filters

We propose a new variant of Accepting Networks of Evolutionary Processors, in which the operations are applied at arbitrary positions to the processed words (rather than at the ends of words only) and where the filters are languages from several special classes of regular sets. More precisely, we show that the use of filters from the class of non-counting, ordered, power-separating, suffix-closed regular, union-free, definite and combinational languages is as powerful as the use of arbitrary regular languages and yields networks that can accept all the recursively enumerable languages. On the other hand, by using filters that are only finite languages, monoids, nilpotent languages, commutative regular languages, or circular regular languages, one cannot generate all recursively enumerable languages. These results seem interesting as they provide both upper and lower bounds on the classes of languages that one can use as filters in an accepting network of evolutionary processors in order to obtain a complete computational model.     

Formal power series and regular operations on fuzzy languages

In this paper we study formal power series over a quantale with coefficients in the algebra of all languages over a given alphabet, and representation of fuzzy languages by these formal power series. This representation generalizes the well-known representation of fuzzy languages by their cut and kernel languages. We show that regular operations on fuzzy languages can be represented by regular operations on power series which are defined by means of operations on ordinary languages. We use power series in study of fuzzy languages which are recognized by fuzzy finite automata and deterministic finite automata, and we study closure properties of the set of polynomials and the set of polynomials with regular coefficients under regular operations on power series.     

多媒体查询语言及其评价准则

随着多媒体技术和多媒体相关应用的发展,对有效检索多媒体信息的要求越来越迫切.查询语言作为信息检索的有效工具,其研究也越来越受到关注.对现有的多媒体查询语言进行了全面的综述,将它们分为两类:专用语言和通用语言.尽管查询语言对多媒体信息系统提供有效的查询服务至关重要,但目前仍没有较好的多媒体查询语言评价准则.因此,针对多媒体查询语言的查询表达能力设计准则共16条,并根据这些准则对多媒体查询语言进行了评价.评价结果表明,这些语言能满足用户的基本查询要求,但在高级语义查询和不确定查询等方面还有欠缺.最后展望了多媒体查询语言的未来研究方向.     

On the equivalence of some transductions involving letter to letter morphisms on regular languages

Summary Equivalence problems of some transductions involving letter to letter morphisms on regular languages are discussed. In particular, we deal with finite substitutions and inverses of finite substitutions. Our main results are the following: (i) The equivalence problem of inverses of finite substitutions on regular languages is undecidable, (ii) The existential equivalence problem of finite substitutions on regular languages is undecidable, and (iii) The length-equivalence problem of finite substitutions on regular languages is decidable.     

ω上下文无关语言和语言的附着之间的关系

文章研究了用重复集生成的ω语言和语言的附着之间的关系,指出并证明了上下文无关语言附着类是ω上下文无关语言类的真子类,正规语言附着类是ω正规语言类的真子类．作为上下文无关语言的一个真子类——线性语言的附着类是ω正规语言类的真子类.     

An infinite hierarchy of intersections of context-free languages

The class of languages expressible as the intersection ofk context-free languages is shown to be properly contained within the class of languages expressible as the intersection ofk + 1 context-free languages. Hence an infinite hierarchy of classes of languages is exhibited between the class of context-sensitive languages and the class of context-free languages.     

Comparative evaluation of high-level real-time programming languages

Owing to the fast growing need for better means of building real-time systems, a number of representative languages used in real-time programming is surveyed. The evaluation focuses on seven languages which possess explicit real-time features. Based on a categorization of the latter, the seven languages are then compared with respect to their real-time capabilities. The strong points and the limitations of Ada and PEARL, the only high-level real-time languages readily applicable in industrial control environments, are covered in more detail. The evaluation reveals that none of the languages actually used in industry is genuinely real-time. Therefore, a number of new features is suggested for incorporation into existing or future languages and their run-time environments. These proposals are meant to advance the inadequate state of affairs, and also to reignite the discussion of this topic in the real-time community.     

Tree Tuple Languages from the Logic Programming Point of View

We introduce inductive definitions over language expressions as a framework for specifying tree tuple languages. Inductive definitions and their subclasses correspond naturally to classes of logic programs, and operations on tree tuple languages correspond to the transformation of logic programs. We present an algorithm based on unfolding and definition introduction that is able to deal with several classes of tuple languages in a uniform way. Termination proofs for clause classes translate directly to closure properties of tuple languages, leading to new decidability and computability results for the latter.     

Decidability of operation problems for T0L languages and subclasses

We investigate the decidability of the operation problem for T0L languages and subclasses. Fix an operation on formal languages. Given languages from the family considered (0L languages, T0L languages, or their propagating variants), is the application of this operation to the given languages still a language that belongs to the same language family? Observe, that all the Lindenmayer language families in question are anti-AFLs, that is, they are not closed under homomorphisms, inverse homomorphisms, intersection with regular languages, union, concatenation, and Kleene closure. Besides these classical operations we also consider intersection and substitution, since the language families under consideration are not closed under these operations, too. We show that for all of the above mentioned language operations, except for the Kleene closure, the corresponding operation problems of 0L and T0L languages and their propagating variants are not even semidecidable. The situation changes for unary 0L languages. In this case we prove that the operation problems with respect to Kleene star, complementation, and intersection with regular sets are decidable.     

A comparison of object-oriented programming in four modern languages

Object-oriented programming has become a widely used, important programming paradigm that is supported in many different languages. C++ has become the most widely used object-oriented language and many C++ programmers are unfamiliar with the different approaches taken by other languages in the paradigm. This paper is intended as an introduction to a broad range of ideas in object-oriented programming. Specifically, we introduce four modern programming languages that support object-oriented programming (Oberon-2, Modula-3, Sather and Self), and show how a simple application is coded in these languages. While each of these programming languages provide support for inheritance, dynamic dispatch, code reuse, and information hiding, they do so in very different ways and with varying levels of efficiency and simplicity. The use of a simple example, based on a common programming problem, facilitates our comparison. We have coded the application in all of these languages, including C++, and we compare the compile times, object code sizes, and run times of the available implementations. Implementations of all the languages compared and all of the programs we measure are available on the Internet. Ultimately, our goal is to encourage and facilitate programmers in understanding and exploring a variety of object-oriented programming languages.     

脚本语言发展研究

一、引言在过去30年里,编程人员在编写程序的过程中更多注重的是如何使用高级程序设计语言编写出具有个性的应用程序,但这一观念目前正逐步发生了根本性的变化。这种变化表现为由高级程序设计语言(例如C或C~( ))向脚本语言(例如Perl或TcL)的过渡。因此,比较脚本语言和高级程序设计语言的各自特点有利于我们了解这种变化的必然性。     

函数式逻辑语言的操作语义

函数式语言和逻辑语言在下列意义上是互补的,基于归约的函数式程序设计语言具有确定和懒惰求解等性质.但同时它又缺少诸如存在量化的变量以及部分数据结构等所希望的性质.相反,基于HORN子句逻辑和消解原理的逻辑程序设计语言允许存在量化的变量和部分数据结构但又缺少确定和懒惰求解的性质.从这个角度出发,把函数和逻辑程序设计语言结合成一种范型是很自然的,这种结合提供了一种比逻辑和函数语言表达能力更强的合一语言.提出了函数式逻辑语言的操作语义,同时表明这种操作语义在实践中是可见的.     

Syntax and semantics of universal programming languages

This paper deals with certain characterizations of the sets of positive integers which when represented as strings on a finite alphabet, form tree adjunct languages, As the context free languages constitute a subfamily of tree adjunct languages, the results carry over to the former as well.     

On function languages and parallel computers

This paper is a discussion of functional languages and parallel computers. It is aimed at an audience that has a background in computer architecture, but not necessarily in the area of functional languages. It therefore constitutes an introductory survey of functional languages, on the one hand, and a non-introductory discussion of parallel computers, on the other. The aim is to highlight some important issues regarding the use of adequacy of these languages and also on the design of parallel computers to interpret them. The concluding thesis of put forth is twofold: one, that to widen their scope of applicability, functional languages need to include more features of nondeterminism and may need to be integrated with features from conventional languages; two, that the right sort of architectures for such extended languages may well be less-specialised ones with a von Neumann flavour.     

The complexity of the membership problem for some extensions of context-free languagest†

The time and tape complexity of some families of languages defined in the literature by altering methods of generation by context-free grammars is considered. Specifically; it is shown that the following families of languages can be recognized by deterministic multitape Turing machines either in polynomial time or within (log n)² tape:

1) the context independent developmental (EOL) languages;

2) the simple matrix languages;

3) the languages generated by derivation restricted state grammars.:

4) the languages generated by linear context-free grammars with certain non-regular control sets;

5) the languages generated by certain classes of vector grammars.

In fact, these languages are of the same tape complexity as context-free languages. Other results indicate the complexity of EDOL languages and the effects on complexity of applying the homomorphic replication operator to regular and context-free languages.     

Principles for modeling language design

Modeling languages, like programming languages, need to be designed if they are to be practical, usable, accepted, and of lasting value. We present principles for the design of modeling languages. To arrive at these principles, we consider the intended use of modeling languages. We conject that the principles are applicable to the development of new modeling languages, and for improving the design of existing modeling languages that have evolved, perhaps through a process of unification. The principles are illustrated and explained by several examples, drawing on object-oriented and mathematical modeling languages.