Context-free complexity of finite languages

In this paper the investigation of the theory of grammatical complexity as started by Bucher (1981) and Bucher, Culik II, Maurer and Wotschke (1981) is continued. The basic question we are concerned with is the following: Given some finite language L, what is the smallest number of context-free productions needed to generate L, the so-called (context-free) complexity of L. We strengthen some of the results given by Bucher et al. (1981), the main result being a necessary condition for certain sequences of finite languages to be of sublinear complexity.     

Context-sensitive immediate constituent analysis: Context-free languages revisited

The ability of context-sensitive grammars togenerate non-context-free languages is well known. However, phrase-structure rules are often used in both natural and artificial languages, not to generate sentences, but rather toanalyze or parse given putative sentences. Linguistic arguments have been advanced that this is the more fruitful use of CS rules for natural languages, and that, further, it is the purported phrasestructure tree which is presented and analyzed, rather than merely the terminal string itself. In this interpretation, for example the rules {S AB, A a/__b, B b/ a__} parse the sentenceab for they analyze the tree represented by the labeled bracketing [_S[_Aa]_A[_Bb]_B]_S, even though these rules do not generateab when interpreted as a CS grammar.We shall say that a languageL is parsed by the finite setR of context-sensitive rules ifL consists of the terminal strings of trees analyzed byR. An actual parsing of an artificial language might be obtained, for example, by using a standard parsing algorithm for the associated CF grammar (obtained by deleting all contexts from rules) to generate putative trees and then analyzing these trees with the given CS grammar. In this paper, a language is shown to becontext-free if and only if there is a finite set ofcontext-sensitive rules which parse this language; i.e., if and only if there is a collection of trees whose terminal strings are the sentences of this language and a finite set of CS rules which analyze exactly these trees.This work was supported in part by the 1968 Advanced Research Seminar in Mathematical Linguistics, sponsored by the Mathematical Social Science Board, Center for Advanced Study in the Behavioral Sciences. The authors wish also to acknowledge their debt to Dr. Robert E. Wall for several helpful and stimulating conversations about this material. It was presented at the Association for Computing Machinery Symposium on the Theory of Computing held in Marina del rey, California in May 1969.     

Context-free languages can be accepted with absolutely no space overhead

We study Turing machines that are allowed absolutely no space overhead. The only work space the machines have, beyond the fixed amount of memory implicit in their finite-state control, is that which they can create by cannibalizing the input bits’ own space. This model more closely reflects the fixed-sized memory of real computers than does the standard complexity-theoretic model of linear space. Though some context-sensitive languages cannot be accepted by such overhead-free machines, we show that all context-free languages can be accepted nondeterministically in polynomial time with absolutely no space overhead, and that all deterministic context-free languages can be accepted deterministically in polynomial time with absolutely no space overhead.     

Strategical languages of infinite words

We deal in this paper with strategical languages of infinite words, that is those generated by a nondeterministic strategy in the sense of game theory. We first show the existence of a minimal strategy for such languages, for which we give an explicit expression. Then we characterize the family of strategical languages as that of closed ones, in the topological space of infinite words. Finally, we give a definition of a Nash equilibrium for such languages, that we illustrate with a famous example.     

Context-free graph languages of bounded degree are generated by apex graph grammars

The apex graph grammars generate precisely the context-free graph languages of bounded degree, independently of whether one considers hyperedge replacement systems or (boundary or confluent) NLC or edNCE graph grammars. The main feature of apex graph grammars is that nodes cannot be passed from nonterminal to nonterminal. The proof is based on a normal form result for arbitrary hyperedge replacement systems that forbids passing chains. This generalizes Greibach Normal Form.     

Finite n-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.

Eilenberg, Elgot and Shepherdson showed in 1969, [S. Eilenberg, C.C. Elgot, J.C. Shepherdson, Sets recognized by n$n$-tape automata, Journal of Algebra 13 (1969) 447–464], that a relation on finite words over a finite, non-unary alphabet with p$p$ letters is definable in first order logic with p+2$p+2$ predicates for the relations equal length, prefix and last letter is  a$a$ (for each letter a∈Σ$a\in \Sigma$) if and only if it can be recognized by a finite multitape synchronous automaton, i.e., one whose read heads move simultaneously. They left open the characterization in the case of infinite alphabets, and proposed some conjectures concerning them. We solve all problems and sharpen the main theorem of [S. Eilenberg, C.C. Elgot, J.C. Shepherdson, Sets recognized by n$n$-tape automata, Journal of Algebra 13 (1969) 447–464].     

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.     

Default theories over monadic languages

In this paper we compare the semantical and syntactical definitions of extensions for open default theories. We prove that, over monadic languages, these definitions are equivalent and do not depend on the cardinality of the underlying infinite world. We also show that, under the domain closure assumption, one free variable open default theories are decidable.     

Context-free text grammars

A text is a triple=(, ₁, ₂) such that is a labeling function, and ₁ and ₂ are linear orders on the domain of ; hence may be seen as a word (, ₁) together with an additional linear order ₂ on the domain of . The order ₂ is used to give to the word (, ₁) itsindividual hierarchical representation (syntactic structure) which may be a tree but it may be also more general than a tree. In this paper we introducecontext-free grammars for texts and investigate their basic properties. Since each text has its own individual structure, the role of such a grammar should be that of a definition of a pattern common to all individual texts. This leads to the notion of ashapely context-free text grammar also investigated in this paper.     

Efficient unification over infinite terms

We address the unification problem for expressions over infinite first-order terms. An algorithm which is practically linear in time and space is presented. It is argued that this algorithm is better than some recent algorithms with respect to performance in practice and simplicity in nature. It is further argued that this superiority also holds in comparison with some of the best known algorithms for the more conventional unification problem over finite terms.     

Context-free preserving functions

A functionf on the non-negative integers is a context-free preserving function (cfpf) if and only if for every context-free languageL, {x|(y) (xy L, and |y| =f(|x|))} is a context-free language. In this note we give an algebraic characterization of the class of cfpf's.This research was supported by the National Bureau of Standards under Contract 3-35999.     

Context-free insertion–deletion systems

We consider a class of insertion–deletion systems which have not been investigated so far, those without any context controlling the insertion–deletion operations. Rather unexpectedly, we found that context-free insertion–deletion systems characterize the recursively enumerable languages. Moreover, this assertion is valid for systems with only one axiom, and also using inserted and deleted strings of a small length. As direct consequences of the main result we found that set-conditional insertion–deletion systems with two axioms generate any recursively enumerable language (this solves an open problem), as well as that membrane systems with one membrane having context-free insertion–deletion rules without conditional use of them generate all recursively enumerable languages (this improves an earlier result). Some open problems are also formulated.     

推导可交换上下文无关语言

提出了推导可交换上下文无关语言及其文法,证明了正规语言类和有界上下文无关语言类都是推导可交换上下文无关语言类的子集,而推导可交换上下文无关语言类是上下文无关语言类的一个子集;定义了该类语言的α闭包等有关运算,给出了推导可交换上下文无关语言表达式,证明了推导可交换上下文无关文法、推导可交换上下文无关语言表达式之间的等价转换.     

There is no fully abstract fixpoint semantics for non-deterministic languages with infinite computations

It is well known that for many non-deterministic programming languages there is no continuous fully abstract fixpoint semantics. This is usually attributed to “problems with continuity”, that is, the assumption that the semantic functions should be continuous supposedly plays a role in the difficulties of giving a fully abstract fixpoint semantics. We show that for a large class of non-deterministic programming languages there is no fully abstract least fixpoint semantics even if one considers arbitrary functions (not necessarily continuous) over arbitrary partial orders (not necessarily complete).