Emerald: A general-purpose programming language

Emerald is a general-purpose language with aspects of traditional object-oriented languages, such as Smalltalk, and abstract data type languages, such as Modula-2 and Ada. It is strongly typed with a non-traditional object model and type system that emphasize abstract types, allow separation of typing and implementation, and provide the flexibility of polymorphism and subtyping with compile-time checking. This paper describes the Emerald language and its programming methodology. We give examples that demonstrate Emerald's features, and compare and contrast the Emerald approach to programming with the approaches used in other similar languages.     

Derivation languages of grammar forms†

The family of derivation languages or Szilard languages associated with a grammar form is studied. It is shown that Szilard equivalence, regular completeness and regular sufficiency are decidable properties. Although the decidability of left Szilard equivalence remains open, we reduce this problem to the equivalence problem for a special class of s-grammar forms     

Relations between Gold-style learning and query learning

Different formal learning models address different aspects of human learning. Below we compare Gold-style learning—modelling learning as a limiting process in which the learner may change its mind arbitrarily often before converging to a correct hypothesis—to learning via queries—modelling learning as a one-shot process in which the learner is required to identify the target concept with just one hypothesis. In the Gold-style model considered below, the information presented to the learner consists of positive examples for the target concept, whereas in query learning, the learner may pose a certain kind of queries about the target concept, which will be answered correctly by an oracle (called teacher). Although these two approaches seem rather unrelated at first glance, we provide characterisations of different models of Gold-style learning (learning in the limit, conservative inference, and behaviourally correct learning) in terms of query learning. Thus we describe the circumstances which are necessary to replace limit learners by equally powerful one-shot learners. Our results are valid in the general context of learning indexable classes of recursive languages. This analysis leads to an important observation, namely that there is a natural query learning type hierarchically in-between Gold-style learning in the limit and behaviourally correct learning. Astonishingly, this query learning type can then again be characterised in terms of Gold-style inference.     

A note on Lindenmayer systems,Szilard languages,spectra, and equivalence

We investigate the Szilard languages and the spectra of Lindenmayer systems through the generalization of Lindenmayer systems toK-iteration grammars and context-sensitiveK-iteration grammars. Various decidability and undecidability results are presented with respect to the evaluation of Szilard languages and spectra for particularK-iteration grammars. Further, two different definitions of the Szilard and spectral equivalence of twoK-iteration grammars are investigated.Work carried out under a National Research Council of Canada Grant No. A-7700.     

Data schemata based on directed graphs

Rooted, labeled, directed graphs (RLDs) are taken as the basis for describing data structures. A constructive formalism is set up to describe RLDs, generate them by means of grammars, and carry out operations such as accessing nodes, inserting and deleting data items, and recognizing graph patterns. It is shown how the formalism can be translated into languages for data definition and data manipulation, of the type associated with data-base systems. The availability of the formalism allows a systematic development of such languages, and provides a method of incorporating consistency preconditions to structural operations and proving the correctness of the data structures that arise in using such languages.     

Expanded subalphabets in the theories of languages and semigroups†

A new type of code, called an expanded subalphabet, is introduced. It is shown that the following four conditions on a subset L of the free monoid A ^? over a finite or infinite alphabet A are equivalent: (1) L is the submonoid generated by an expanded subalphabet; (2) L is a retract; (3) L is the fixed language of an endomorphism; (4) L is the stationary language of an endomorphism. Expanded subalphabets are used as a tool for the investigation of fixed languages (=retracts). Special results for the case of a finite alphabet are given and the relationship with the theory of L-systems is indicated.     

A visual language‐based system for extraction–transformation–loading development

Data warehouse loading and refreshment is typically performed by means of complex software processes called extraction–transformation–loading (ETL). In this paper, we propose a system based on a suite of visual languages for mastering several aspects of the ETL development process, turning it into a visual programming task. The approach can be easily generalized and applied to other data integration contexts beyond data warehouses. It introduces two new visual languages that are used to specify the ETL process, which can also be represented by means of UML activity diagrams. In particular, the first visual language supports data manipulation activities, whereas the second one provides traceability information of attributes to highlight the impact of potential transformations on integrated schemas depending on them. Once the whole ETL process has been visually specified, the designer might invoke the automatic generation of an activity diagram representing a possible orchestration of it based on its dependencies. The designer can edit such a diagram to modify the proposed orchestration provided that changes do not alter data dependencies. The final specification can be translated into code that is executable on the data sources. Finally, the effectiveness of the proposed approach has been validated through a user study in which we have compared the effort needed to design an ETL process in our approach with respect to the one required with main visual approaches described in the literature.Copyright © 2013 John Wiley & Sons, Ltd.     

A strongly primitive word of arbitrary length and its application †

It is known that both the class of all (n,k)-languages and the class of all time-variant languages over a finite alphabet contain the class of all regular languages. In this paper we show that in general neither one of these two classes of languages contains the other by constructing an infinite sequence of strongly primitive words over an alphabet with four letters.     

The context-splittable normal form for Church–Rosser language systems

In this paper the context-splittable normal form for rewriting systems defining Church–Rosser languages is introduced. Context-splittable rewriting rules look like rules of context-sensitive grammars with swapped sides. To be more precise, they have the form uvw→uxw with u,v,w being words, v being nonempty and x being a single letter or the empty word. It is proved that this normal form can be achieved for each Church–Rosser language and that the construction is effective. Some interesting consequences of this characterization are given, too.     

On the language equivalence of NE star-patterns

A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting (non-empty) strings for variables. The pattern languages are one of language family which is orthogonal to the Chomsky-type languages hierarchy. They have many applications, such as the extended regular expressions, for instance, in languages Perl, awk, etc. They are well applicable in machine learning as well. There are erasing and non-erasing patterns are used. For non-erasing pattern languages the equivalence of languages is decidable but the inclusion problem for them is undecidable. In extended regular expressions one can use union, concatenation and Kleene star to make more complex patterns. It is also known, that the equivalence problem of extended regular expressions is undecidable. However, the problem, whether the equivalence is decidable for patterns using only concatenation and star still open. In this paper there are some interesting results about inclusion properties and equivalences of some kinds of erasing and non-erasing pattern languages. We show that the equivalence problem of non-erasing patterns in some cases can be reduced to the decidability problem of some very special inclusion properties. These results may be useful to decide whether the language equivalence of non-erasing star-patterns is decidable or not.     

Programming Languages For Interactive Computing

Traditional programming languages are algorithmic: they are best suited to writing programs that acquire all their inputs before executing and only produce a result on termination. By contrast most applications are interactive: they maintain ongoing interactions with their environments. Modern systems address this incompatibility by manually extending the execution model of the host language to support interaction, usually by embedding an event-driven state management scheme which executes fragments of imperative code in response to interactions, the job of each executed fragment being to restore the internal consistency of the computation. The downside of this approach to interaction is that it relies heavily on mutable stores and side-effects and mixes application logic in with behaviour which is more properly the responsibility of an execution model. I describe a programming model called declarative interaction which supports interaction directly. The distinguishing feature of the model is its modal construal of state and interaction.     

Mkscan—An interactive scanner generator

Mkscan is a tool for generating and editing scanners. It has been designed with ease of use in mind. The tol is interactive and uses a full screen interface. No attempt is made to provide an all-purpose tool that can generate a recognizer for any regular language. Instead, mkscan has been tailored to suit the lexical structure of common programming languages and command languages. Using mkscan, a scanner for Pascal can be created in under ten minutes–including the time taken to type the list of keywords.     

On the complexity of the instance checking problem in concept languages with existential quantification

Most of the work regarding complexity results for concept languages consider subsumption as the prototypical inference. However, when concept languages are used for building knowledge bases including assertions on individuals, the basic deductive service of the knowledge base is the so-called instance checking, which is the problem of checking if an individual is an instance of a given concept. We consider a particular concept language, calledALE, and we address the question of whether instance checking can be really solved by means of subsumption algorithms in this language. Therefore, we indirectly ask whether considering subsumption as the prototypical inference is justified. Our analysis, carried out considering two different measure of complexity, shows that inALE instance checking is strictly harder than subsumption. This result singles out a new source of complexity in concept languages, which does not show up when checking subsumption between concepts.This work has been supported by the ESPRIT Basic Research Action N.6810-COMPULOG 2 and by the Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo of the CNR (Italian Research Council).     

Highly Constrained Unification Grammars

Unification grammars are widely accepted as an expressive means for describing the structure of natural languages. In general, the recognition problem is undecidable for unification grammars. Even with restricted variants of the formalism, off-line parsable grammars, the problem is computationally hard. We present two natural constraints on unification grammars which limit their expressivity and allow for efficient processing. We first show that non-reentrant unification grammars generate exactly the class of context-free languages. We then relax the constraint and show that one-reentrant unification grammars generate exactly the class of mildly context-sensitive languages. We thus relate the commonly used and linguistically motivated formalism of unification grammars to more restricted, computationally tractable classes of languages.     

Stochastic Finite Learning of the Pattern Languages

The present paper proposes a new learning model—called stochastic finite learning—and shows the whole class of pattern languages to be learnable within this model.This main result is achieved by providing a new and improved average-case analysis of the Lange–Wiehagen (New Generation Computing, 8, 361–370) algorithm learning the class of all pattern languages in the limit from positive data. The complexity measure chosen is the total learning time, i.e., the overall time taken by the algorithm until convergence. The expectation of the total learning time is carefully analyzed and exponentially shrinking tail bounds for it are established for a large class of probability distributions. For every pattern containing k different variables it is shown that Lange and Wiehagen's algorithm possesses an expected total learning time of , where and are two easily computable parameters arising naturally from the underlying probability distributions, and E[] is the expected example string length.Finally, assuming a bit of domain knowledge concerning the underlying class of probability distributions, it is shown how to convert learning in the limit into stochastic finite learning.     

Formal language identification: query learning vs. Gold-style learning

A natural approach towards powerful machine learning systems is to enable options for additional machine/user interactions, for instance by allowing the system to ask queries about the concept to be learned. This motivates the development and analysis of adequate formal learning models.In the present paper, we investigate two different types of query learning models in the context of learning indexable classes of recursive languages: Angluin's original model and a relaxation thereof, called learning with extra queries. In the original model the learner is restricted to query languages belonging to the target class, while in the new model it is allowed to query other languages, too. As usual, the following standard types of queries are considered: superset, subset, equivalence, and membership queries.The learning capabilities of the resulting query learning models are compared to one another and to different versions of Gold-style language learning from only positive data and from positive and negative data (including finite learning, conservative inference, and learning in the limit). A complete picture of the relation of all these models has been elaborated. A couple of interesting differences and similarities between query learning and Gold-style learning have been observed. In particular, query learning with extra superset queries coincides with conservative inference from only positive data. This result documents the naturalness of the new query model.     

Design of an arabic programming language (ARABLAN)

It was observed that school children in Arab countries find difficulty in learning programming in a language other than their native language. There are only few Arabic programming languages in the literature; most of which are never or partially implemented. In this paper, we present the design of a new Arabic programming language (ARABLAN) which is planned to be implemented for use in teaching programming for school children in Arab countries.