Generalised Stream X-Machines with Output Delimited Type

Some conditions relating to the automata involved in the W-testing method are discussed. It is also shown how to use the method for reduced automata instead of minimal automata. New design test conditions (weak output distinguishable, strong test-complete and output delimited type) are considered for the generalised stream X-machines (stream X-machines with basic functions replaced by relations and having as output strings of symbols rather than single symbols). It is proved that testing methods similar to those already developed for ordinary deterministic stream X-machines may be applied for generalised stream X-machines with output delimited types. A particular case of generalised stream X-machine with output delimited type is the X-machine with output delimiter, which produces outputs having a distinct right end character. Received October 2000 / Accepted in revised form January 2001     

Left-forbidding cooperating distributed grammar systems

A left-forbidding grammar, introduced in this paper, is a context-free grammar, where a set of nonterminal symbols is attached to each context-free production. Such a production can rewrite a nonterminal provided that no symbol from the attached set occurs to the left of the rewritten nonterminal in the current sentential form. The present paper discusses cooperating distributed grammar systems with left-forbidding grammars as components and gives some new characterizations of language families of the Chomsky hierarchy. In addition, it also proves that twelve nonterminals are enough for cooperating distributed grammar systems working in the terminal derivation mode with two left-forbidding components (including erasing productions) to characterize the family of recursively enumerable languages.     

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.     

Control sets on grammars using depth-first derivations

Control sets on grammars are extended to depth-first derivations. It is proved that a context-free language is generated by the depth-first derivations of an arbitrary context-free grammar controlled by an arbitrary regular set. This result is sharpened to obtain a new characterization of the family of derivation-bounded languages: a languageL is derivation bounded if and only if it is generated by the depth-first derivations of a context-free grammarG controlled by a regular subsetR of the Szilard language ofG. The left-derivation-bounded languages are characterized analogously using leftmost derivations. It is proved that a grammarG is nonterminal bounded if and only if the Szilard language defined using only the depth-first derivations ofG is regular. Finally, it is proved that if a family of languagesC is a trio, a semi-AFL, an AFL, or an AFL closed under -free substitution, then the family of languages generated using arbitrary context-free grammars controlled by members ofC is full, is closed under reversal, and has the closure properties assumed ofC.     

Look-ahead on pushdowns

The general notion of look-ahead on pushdowns is used to prove that (1) the deterministic iterated pushdown languages are closed under complementation, (2) the deterministic iterated pushdown languages are properly included in the non-deterministic iterated pushdown languages; the counter example is a very simple linear context-free language, independent of the amount of iteration, (3) LL(k) iterated indexed grammars can be parsed by deterministic iterated pushdown automata, and (4) it is decidable whether an iterated indexed grammar is LL(k). Analogous results hold for iterated pushdown automata with regular look-ahead on the input, and LL-regular iterated indexed grammars.     

Editorial

Formal Aspects of Computing marks the end of the first year of our re-launched format. It has not been an easy year either for the editors or for the ever-patient staff at Springer-Verlag; but it has certainly been successful with first class papers being published soon after acceptance. As with most computing journals, refereeing poses a (potential) bottleneck to getting an author's ideas into print but even here our colleagues at Springer-Verlag have come up with an incentive scheme from which our future referees will benefit and hopefully speed the refereeing process to everyone's advantage. Recently, most editions of the journal have been standard issues with a number of submitted papers. It has been our stated intention since the journal began to have special editions with whole editions on a single topic. We are currently planning such a special edition to mark Rod Burstall's retirement (in fact we have so many excellent papers that there will probably have to be a double edition). This special issue collects a number of papers on X-machines edited by Mike Holcombe and myself. Mike has written a brief introduction and there follow five papers which have all been refereed by experts in the area (I took personal charge of having Mike's paper refereed). The generalisation of the testing theory to non-deterministic stream X-machines is the focus of two articles. Non-determinism can be generalised in several ways. R. Hierons and M. Harman look at quasi-non-deterministic machines and describe an approach to dealing with the generation of test sets for such machines. F. Ipate and M. Holcombe look at another way to view non-determinism and also focus on test set generation, the issue of fairness becomes important if the strong claims about fault detection by the test sets are to be achieved. M. Gheorghe has investigated how a collection of formal grammars can be controlled by a type of generalised stream X-machine so that the languages generated by such a system of grammars can be determined. He has shown that relatively simple grammars can generate very complex languages using this approach. T. Balanescu explores further generalisations of Stream X-machines and discusses how the design for test conditions can be adapted for a specific type of machine. A. Cowling et al. look at communicating X-machine systems and consider how this approach can be used to model message passing using a simple communicating matrix metaphor. Models built this way can be used to generate, automatically, concurrent programs. In a paper to appear in Volume 13, F. Ipate and M. Holcombe look at how the test theory can be adapted to apply to the communicating X-machines systems case. Indeed, Volume 13 already looks to be an exciting mix of scientific contributions – we also expect to back on a more regular publication schedule by the end of 2001.     

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.     

On the number of components in cooperating distributed grammar systems

It is proved that the number of components in context-free cooperating distributed (CD) grammar systems can be reduced to 3 when they are working in the so-called sf-mode of derivation, which is the cooperation protocol which has been considered first for CD grammar systems. In this derivation mode, a component continues the derivation until and unless there is a nonterminal in the sentential form which cannot be rewritten according to that component. Moreover, it is shown that CD grammar systems in sf-mode with only one component can generate only the context-free languages but they can generate non-context-free languages if two components are used. The sf-mode of derivation is compared with other well-known cooperation protocols with respect to the hierarchies induced by the number of components.     

Tree controlled grammars

Languages are studied which can be generated by context-free grammars under a single simple restriction which must be satisfied by its derivation trees. Using tree controlled grammars (TC grammars for short) all unambigous and some inherently ambigous context-free languages, and also some non context-free languages can be parsed in timeO(n ²). The classes of regular, linear, context-free, EOL, ETOL and type 0 languages can be characterized in a natural manner using TC grammars. A context-free generator for all type 0 languages is exhibited. Some normal forms for TC grammars are established but it is shown that many common normal forms (e. g. Greibach normal form) cannot be obtained for TC grammars in general.     

Closure properties of linear context-free tree languages with an application to optimality theory

Context-free tree grammars, originally introduced by Rounds [Math. Systems Theory 4(3) (1970) 257–287], are powerful grammar devices for the definition of tree languages. The properties of the class of context-free tree languages have been studied for more than three decades now. Particularly important here is the work by Engelfriet and Schmidt [J. Comput. System Sci. 15(3) (1977) 328–353, 16(1) (1978) 67–99]. In the present paper, we consider a subclass of the class of context-free tree languages, namely the class of linear context-free tree languages. A context-free tree grammar is linear, if no rule permits the copying of subtrees. For this class of linear context-free tree languages we show that the grammar derivation mode, which is very important for the general class of context-free tree languages, is immaterial. The main result we present is the closure of the class of linear context-free tree languages under linear frontier-to-root tree transduction mappings. Two further results are the closure of this class under linear root-to-frontier tree transduction mappings and under intersection with regular tree languages.     

Generating Test Sets from Non-Deterministic Stream X-Machines

X-machines were proposed by Holcombe as a possible specification language and since then a number of further investigations have demonstrated that the model is intuitive and easy to use as well as general enough to cater for a wide range of applications. In particular (generalised) stream X-machines have been found to be extremely useful as a specification method and most of the theory developed so far has concentrated on this particular class of X-machines. Furthermore, a method for testing systems specified by stream X-machines exists and is proved to detect all faults of the implementation provided that the system meets certain initial requirements. However, this method can only be used to generate test sequences from deterministic X-machine specifications. In this paper we present the theoretical basis for a method for generating test sets from non-deterministic generalised stream X-machines. Received November 1999 / Accepted in revised form September 2000     

A note on cooperating distributed grammar systems working in combined modes

We investigate the generative power of cooperating distributed grammar systems with context-free rules working in the full-competence mode in combination with another derivation mode, combined sf-mode, for short. A combined sf-mode as, for example, (sf∧?k) restricts the valid derivations such that both properties have to be satisfied. If erasing rules are allowed, then except for the (sf∧?1)-, (sf∧=1)-, and (sf∧t)-modes, it is shown that the family of recursively enumerable languages is characterized. The former two exceptions characterize the family of linear context-free languages, while the latter mode describes the family of context-free languages.     

Controlled bidirectional grammars

We investigate context-free grammars the rules of which can be used in a productive and in a reductive fashion, while the application of these rules is controlled by a regular language. We distinguish several modes of derivation for this kind of grammar. The resulting language families (properly) extend the family of context-free languages. We establish some closure properties of these language families and some grammatical transformations which yield a few normal forms for this type of grammar. Finally, we consider some special cases (viz. the context-free grammar is linear or left-linear), and generalizations, in particular, the use of arbitrary rather than regular control languages.     

Self-embedded context-free grammars with regular counterparts

In general, it is undecidable if an arbitrary context-free grammar has a regular solution. Past work has focused on special cases, such as one-letter grammars, non self-embedded grammars and the finite-language grammars, for which regular counterparts have been proven to exist. However, little is known about grammars with the self-embedded property. Using systems of equations, we highlight a number of subclasses of grammars, with self-embeddedness terms, such as and , that can still have regular languages as solutions. Constructive proofs that allow these subclasses of context-free grammars to be transformed to regular expressions are provided. We also point out a subclass of context-free grammars that is inherently non-regular. Our latest results can help demarcate more precisely the known boundaries between the regular and non-regular languages, within the context-free domain.Received: 17 January 2003, Published online: 17 February 2004Stefan Andrei: stefan@infoiasi.ro     

Testing Conformance to a Quasi-Non-Deterministic Stream X-Machine

Stream X-machines have been used in order to specify a range of systems. One of the strengths of this approach is that, under certain well-defined conditions, it is possible to produce a finite test that is guaranteed to determine the correctness of the implementation under test (IUT). Initially only deterministic stream X-machines were considered in the literature. This is largely because the standard test algorithm relies on the stream X-machine being deterministic. More recently the problem of testing to determine whether the IUT is equivalent to a non-deterministic stream X-machine specification has been tackled. Since non-determinism can be important for specifications, this is an extremely useful extension. In many cases, however, we wish to test for a weaker notion of correctness called conformance. This paper considers a particular form of non-determinism, within stream X-machines, that will be called quasi-non-determinism. It then investigates the generation of tests that are guaranteed to determine whether the IUT conforms to a quasi-non-deterministic stream X-machine specification. The test generation algorithm given is a generalisation of that used for testing from a deterministic stream X-machine. Received November 1999 / Accepted in revised form December 2000     

Abstract families of context-free grammars

An abstract family of grammars (AFG) may be defined as a class of grammars for which the corresponding class of languages forms an abstract family of languages (AFL) as defined by Ginsburg and Greibach. The derivation bounded grammars of Ginsburg and Spanier is an example of an AFG which is properly included in the class of all context-free grammars (also AFG). The main result is that there exist two distinct infinite hierarchies of AFG which exhaust the derivation bounded AFG such that the AFL associated with the kth member of one of these AFG hierarchies is properly included in the AFL associated with the k-lst member of that same hierarchy. Each hierarchy is shown to be strongly incomparable to the other; that is, the first member of each generates some language not generated by a fixed but arbitrary member of the other. We designate these hierarchies as the hierarchies of left and right dominant grammars (languages)     

Hierarchy of k-context-free languages part 1

Languages generated by context-free grammars by rewriting always exactly k nonterminals simultaneouslyk ≥ 1, are called k-context-free languages. We prove a pumping result for k-context-free languages and using it show that the families of k-languages form a strict hierarchy with respect to k.

The paper is divided into two parts. The main results showing the strictness of the hierarchy of k-languages are presented in Part 2. This first part contains definitions and preliminary results on derivation forests and k-schedules.     

Time-bounded controlled bidirectional grammars

We study regularly controlled bidirectional (RCB) grammars from the viewpoint of time-bounded grammars. RCB-grammars are context-free grammars of which the rules can be used in a productive and in a reductive fashion, while the application of these rules is controlled by a regular language. Several modes of derivation can be distinguished for this kind of grammar. A time bound on such a grammar is a measure of its derivational complexity. For some families of time bounds and for some modes of derivation we establish closure properties and a normal form theorem. In addition parsing algorithms are given for some modes of derivation. We conclude with considering generalizations with respect to the family of control languages and the family of bounding functions..     

Approximation of fuzzy context-free grammars

Fuzzy context-free max- grammar (or FCFG, for short), as a straightforward extension of context-free grammar, has been introduced to express uncertainty, imprecision, and vagueness in natural language fragments. Li recently proposed the approximation of fuzzy finite automata, which may effectively deal with the practical problems of fuzziness, impreciseness and vagueness. In this paper, we further develop the approximation of fuzzy context-free grammars. In particular, we show that a fuzzy context-free grammar under max- compositional inference can be approximated by some fuzzy context-free grammar under max-min compositional inference with any given accuracy. In addition, some related properties of fuzzy context-free grammars and fuzzy languages generated by them are studied. Finally, the sensitivity of fuzzy context-free grammars is also discussed.