Description of developmental languages using recurrence systems

Recurrence systems have been devised to describe formally certain types of biological developments. A recurrence system specifies a formal language associated with the development of an organism. The family of languages defined by recurrence systems is an extension of some interesting families of languages, including the family of context-free languages. Some normal-form theorems are proved and the equivalence of the family of recurrence languages to a previously studied family of developmental languages (EOL-languages) is shown. Various families of developmental and other formal languages are characterized using recurrence systems. Some closure properties are also discussed.     

Macro OL-systemsf macro

Macro OL-systems and two of their subclasses, called FMOL-systems and RMOL-systems are introduced. Macro OL-systems arc motivated by theoretical models for the development of biological organism. Various properties of the families of languages generated by FMOL-systems and RMOL-systems are studied. It is shown that the family of languages generated by RMOL-systems forms the minimal full abstract family of languages containing the family of OL-languages.     

On some families of languages related to developmental systems

OL systems and TOL systems are the simplest mathematical models for the study of the development of biological organisms with or without a variable environment, respectively. This paper contributes to the study of the properties of the languages generated by these systems and by their generalizations. Macro OL (TOL) languages are languages obtained by substituting languages of a given type in OL (TOL) languages. We study properties of certain families of macro OL (TOL) languages in particular we show that they are full AFL's.

We observe that OL, TOL systems and many of their generalizations can be viewed as special classes of index grammars.     

A history of data-flow languages

Data-flow refers both to a language-level paradigm of computation and to a family of processor architectures based on this paradigm. This article elaborates data-flow language issues and the evolution of data-flow languages. In considering limits to the expressive power of these languages, underlying architectural issues are discussed. Although the article attempts to present a complete history of data-flow languages, it concentrates on those languages that specifically belong to this class and have been implemented for a data-flow machine. In many cases, the distinctions between issues of language semantics and machine architecture are unclear. Usually we have found that this reflects the evolution of data-flow, and the close association between language and architecture development. In some sections of the article, it may appear that there is an imbalance in the amount of detail presented when compared with other sections. This imbalance is proportional to the publications and the amount of information readily available for the topics     

Growth properties of power-free languages

The aim of this paper is to survey the area formed by the intersection of two popular lines of research in formal language theory. The first line, originated by Thue in 1906, concerns repetition-free words and languages. The second line is the study of growth functions for words and languages; it can be traced back to the classical papers by Morse and Hedlund on symbolic dynamics (1938, 1940). Growth functions of repetition-free languages have been investigated since the 1980’s. Most of the results are obtained for power-free languages, but some ideas can be applied for languages avoiding patterns and Abelian-power-free languages as well.In this paper, we present key contributions to the area, its state of the art, and conjectures that suggest answers to some natural unsolved problems. Also, we pay much attention to the tools and techniques that made the progress in the area possible.     

Righting software

What tools do we use to develop and debug software? Most of us rely on a full-screen editor to write code, a compiler to translate it, a source-level debugger to correct it, and a source-code control system to archive and share it. These tools originated in the 1970s, when the change from batch to interactive programming stimulated the development of innovative languages, tools, environments, and other utilities we take for granted. Microsoft Research has developed two generations of tools, some of which Microsoft developers already use to find and correct bugs. These correctness tools can improve software development by systematically detecting programming errors.     

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.     

Template-guided DNA recombination

The family of stichotrichous ciliates have received a great deal of study due to the presence of scrambled genes in their genomes. The mechanism by which these genes are descrambled is of interest both as a biological process and as a model of natural computation. Several formal models of this process have been proposed, the most recent of which involves the recombination of DNA strands based on template guides. We generalize this template-guided DNA recombination model proposed by Prescott, Ehrenfeucht and Rozenberg to an operation on strings and languages. We then proceed to investigate the properties of this operation with the intention of viewing ciliate gene descrambling as a computational process.     

Software process modeling languages: A systematic literature review

ContextOrganizations working in software development are aware that processes are very important assets as well as they are very conscious of the need to deploy well-defined processes with the goal of improving software product development and, particularly, quality. Software process modeling languages are an important support for describing and managing software processes in software-intensive organizations.ObjectiveThis paper seeks to identify what software process modeling languages have been defined in last decade, the relationships and dependencies among them and, starting from the current state, to define directions for future research.MethodA systematic literature review was developed. 1929 papers were retrieved by a manual search in 9 databases and 46 primary studies were finally included.ResultsSince 2000 more than 40 languages have been first reported, each of which with a concrete purpose. We show that different base technologies have been used to define software process modeling languages. We provide a scheme where each language is registered together with the year it was created, the base technology used to define it and whether it is considered a starting point for later languages. This scheme is used to illustrate the trend in software process modeling languages. Finally, we present directions for future research.ConclusionThis review presents the different software process modeling languages that have been developed in the last ten years, showing the relevant fact that model-based SPMLs (Software Process Modeling Languages) are being considered as a current trend. Each one of these languages has been designed with a particular motivation, to solve problems which had been detected. However, there are still several problems to face, which have become evident in this review. This let us provide researchers with some guidelines for future research on this topic.     

A prime decomposition theorem for grammatical families

Two basic operations on families of languages, in general, and grammatical families, in particular, are sum (formed by taking unions of member languages) and product (formed by taking unions of pairwise products of member languages). In this paper, a grammatical family is defined to be prime if it is contained in one of two grammatical families whenever it is contained in their product, and the following Prime Decomposition Theorem is then established: Every grammatical family can be represented as a minimal sum of products of primes in a unique way.This theorem leads to a general method for decomposing a grammatical family into simpler ones. A subsequent paper uses this method to obtain a decision procedure for determining whether two grammar forms generate the same grammatical family, as well as a canonical representation for grammatical families.     

Extending the Unified Modeling Language for ontology development

There is rapidly growing momentum for web enabled agents that reason about and dynamically integrate the appropriate knowledge and services at run-time. The dynamic integration of knowledge and services depends on the existence of explicit declarative semantic models (ontologies). We have been building tools for ontology development based on the Unified Modeling Language (UML). This allows the many mature UML tools, models and expertise to be applied to knowledge representation systems, not only for visualizing complex ontologies but also for managing the ontology development process. UML has many features, such as profiles, global modularity and extension mechanisms that are not generally available in most ontology languages. However, ontology languages have some features that UML does not support. Our paper identifies the similarities and differences (with examples) between UML and the ontology languages RDF and DAML+OIL. To reconcile these differences, we propose a modification to the UML metamodel to address some of the most problematic differences. One of these is the ontological concept variously called a property, relation or predicate. This notion corresponds to the UML concepts of association and attribute. In ontology languages properties are first-class modeling elements, but UML associations and attributes are not first-class. Our proposal is backward-compatible with existing UML models while enhancing its viability for ontology modeling. While we have focused on RDF and DAML+OIL in our research and development activities, the same issues apply to many of the knowledge representation languages. This is especially the case for semantic network and concept graph approaches to knowledge representations. Initial sbmission: 16 February 2002 / Revised submission: 15 October 2002 Published online: 2 December 2002     

Some Approaches to, and Illustrations of, Programming Language History

This paper describes some factors in, approaches to, and specific elements of, programming language history. It first lists a number of general factors and approaches which can be used to discuss the history of programming languages. After presenting a life cycle for programming language development, it provides numerous illustrations of programming language history and chronology from many of the viewpoints indicated earlier. There is a brief discussion of relevant literature and a section indicating some of the reasons for the vast proliferation of programming languages. Various charts and lists are included. This paper should be viewed as one approach to considering the history of programming languages, rather than as a history of programming languages per se.     

Formes de langages et de grammaires

Summary This paper is devoted to the study of context-free languages over infinite alphabets. This work can be viewed as a new attempt to study families of grammars, replacing the usual grammar forms and giving a new point of view on these questions. A language over an infinite alphabet or I-language appears as being a model for a family of usual languages; an interpretation is an homomorphism from the infinite alphabet to any finite alphabet. Using this notion of interpretation we can associate to each family of I-languages an image, called its shadow, which is a family of usual languages.The closure properties of families, generalizing to infinite alphabets the family of context-free languages, lead to define rational transductions between infinite alphabets or I-transductions, and then, families of I-languages closed under I-transductions, or I-cones. We study here relations between the closure properties of a family of I-languages and these of its shadow. As a result, we obtain that any union closed rational cone of context-free languages, principal or not, is the shadow of a principal I-cone.This work leads to new results about the classical theory of context-free languages. For instance, we prove that any principal rational cone of context-free languages can be generated by a context-free language, whose grammar has only 6 variables. This work also leads to more general considerations about the adequacy of some generating devices to the generated languages. It appears that the context-free grammars are fair, in a sense that we define, for generating context-free languages but that non-expansive context-free grammars are not for generating non-expansive context-free languages. This point of view raises a number of questions.     

On the generative capacity of context-free matrix forms

This paper deals with the concepts of a matrix form and strict interpretation. By a matrix form we mean a context-free matrix grammar. Via an interpretation mechanism it generates a family of structurally related grammars and these generate a family of languages. We study here the properties of matrix forms as generators for the families of regular, linear and context-free languages. It is for instance shown that an arbitrary matrix form with only one nonterminal symbol does not generate the family of context-free languages if it contains a matrix with at least two productions.     

Pushdown acceptor forms

By analogy with the concept of interpretation of a grammar, the notion of interpretation of a pushdown acceptor is introduced for studying the pushdown-like devices structurally close to a given master pushdown acceptor. The main result established is that the family of languages accepted by those pushdown-like acceptors defined by interpretations of a fixed pushdown acceptor coincide with the family of languages generated by those grammars defined by interpretations of some grammar, and conversely.     

On the automated translational execution of the action language for foundational UML

To manage the rapidly growing complexity of software development, abstraction and automation have been recognised as powerful means. Among the techniques pushing for them, model-driven engineering has gained increasing attention from industry for, among others, the possibility to automatically generate code from models. To generate fully executable code, models should describe complex behaviours. While pragmatically this is achieved by employing programming languages for defining actions within models, the abstraction gap between modelling and programming languages can undermine consistency between models and code as well as analysability and reusability of models. In light of this, model-aware action languages should be preferred. This is the case of the Action Language for Foundational UML (ALF). In this paper, we provide a solution for the fully automated translational execution of ALF towards C++. Additionally, we give an insight on how to simplify the transition from the use of programming languages for modelling fine-grained behaviours to model-aware action languages in industrial MDE. The solution presented in this paper has been assessed on industrial applications to verify its applicability to complex systems as well as its scalability.     

Net-based control versus rational control The relation between ITNC vector languages and rational relations

 An Individual Token Net Controller (or ITNC) is a particular type of state-machine decomposable Petri net that can be used as a synchronization mechanism in concurrent systems consisting of a fixed number of sequential subsystems. In this paper the family of ITNC vector languages is compared to the well-known family of rational relations. On the one hand it is proved that the family of rational relations equals the family of vector languages of Generalized ITNCs, i.e. ITNCs in which the restriction of completeness is dropped. On the other hand a vector language property induced by completeness is identified that precisely characterizes the difference between ITNC vector languages and Generalized ITNC vector languages. In addition, the results are shown to carry over to the prefix-closed versions of the models. Received: 7 August 1990/6 October 1995