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.     

A mechanisation of some context-free language theory in HOL4

We describe the mechanisation of some foundational results in the theory of context-free languages (CFLs), using the HOL4 system. We focus on pushdown automata (PDAs). We show that two standard acceptance criteria for PDAs (“accept-by-empty-stack” and “accept-by-final-state”) are equivalent in power. We are then able to show that the pushdown automata (PDAs) and context-free grammars (CFGs) accept the same languages by showing that each can emulate the other. With both of these models to hand, we can then show a number of basic, but important results. For example, we prove the basic closure properties of the context-free languages such as union and concatenation. Along the way, we also discuss the varying extent to which textbook proofs (we follow Hopcroft and Ullman) and our mechanisations diverge: sometimes elegant textbook proofs remain elegant in HOL; sometimes the required mechanisation effort blows up unconscionably.     

一种特殊的上下文无关文法及其语法分析

SAQ系统是一个进行软件规约获取、检验和复用的实验系统，其中以上下文无关文法表示的概念是规约的一部分.SAQ要求将概念的词法和句法定义结合在一个上下文无关文法中.如果用常规的上下文无关文法描述诸如程序设计语言和自然语言等一些复杂概念的语法，则需要把诸如空格和回车等没有实质意义的分隔符包含到语法中去(这种描述方法称为朴素表示法),使得语法描述很累赘.为此，作者设计了一种特殊的上下文无关文法,它把通常上下文无关文法定义中的非终极符集合和终极符集合进行细化.用这种文法可以相对简洁地描述程序语言和自然语言等复杂概     

One application of real-valued interpretation of formal power series

We define two natural properties of context-free grammars. The first property generalizes linearity and the second property strengthens nonlinearity. A language generated by an unambiguous grammar of the first type is called the language with weak linear structure and a language generated by an unambiguous grammar of the second type is called the language with strong nonlinear structure. Our main theorem states that the family of unambiguous grammars generating languages with weak linear structure and the family of unambiguous grammars generating languages with strong nonlinear structure are effectively separable.     

Permutations are not context-free: An application of the interchange lemma

Let x be a nonempty string and x? another string with the same characters as x, but possibly in a different order. A string of the form xx? is called a permutation. A permutation-containing string is of the form wxx?y. The Interchange Lemma for context-free languages [11] is used to show that the set of permutation-containing strings over a 16 character alphabet is not context-free. The application of the lemma is important since other techniques, such as the pumping lemma and Ogden's lemma cannot show that the set is not context-free. Finally, a collection of open problems is given.     

On the synchronized derivation depth of context-free grammars

We consider depth of derivations as a complexity measure for synchronized and ordinary context-free grammars. This measure differs from the earlier considered synchronization depth in that it counts the depth of the entire derivation tree. We consider (non-)existence of trade-offs when using synchronized grammars as opposed to non-synchronized grammars and establish lower bounds for certain classes of linear context-free languages.     

An undecidable property of context-free linear orders

We prove that there exists no algorithm to decide whether the language generated by a context-free grammar is dense with respect to the lexicographic ordering. As a corollary to this result, we show that it is undecidable whether the lexicographic orderings of the languages generated by two context-free grammars have the same order type.     

Sequential classification of strings generated by SCFG's

A sequential classification algorithm (SCA) for stochastic context-free languages is given. The algorithm is an extension of Earley's parsing algorithm for context-free languages. The SCA uses an optimum decision rule and a suboptimal stopping rule. The time bound is proportional ton ³ (n is the length of the string). A parametere* in the SCA allows an easy control over the probability of error. It is shown theoretically and experimentally that a considerable amount of processing time can be saved when using the SCA compared to the time required when using Earley's algorithm.This work was supported by the AFOSR Grant 74–2661.     

Splicing on tree-like structures

In this paper, we provide a method to increase the power of splicing systems. We introduce the splicing systems on trees to be built as partially annealed single strands, which is a quite similar notion and a natural extension of splicing systems on strings. Trees are a common and useful data structure in computer science and have a biological counterpart such as molecular sequences with secondary structures, which are typical structures in RNA sequences. Splicing on trees involves (1) complete subtrees as axioms, (2) restriction operated on the annealed subsequences, (3) rules to substitute a complete subtree with another. We show that splicing systems on trees with finite sets of axioms and finite sets of rules can generate the class of context-free languages without the need of imposing multiplicity constraints.     

Generalized one-sided forbidding grammars

In generalized one-sided forbidding grammars (GOFGs), each context-free rule has associated a finite set of forbidding strings, and the set of rules is divided into the sets of left and right forbidding rules. A left forbidding rule can rewrite a nonterminal if each of its forbidding strings is absent to the left of the rewritten symbol. A right forbidding rule is applied analogically. Apart from this, they work like any generalized forbidding grammar. This paper proves the following three results. (1) GOFGs where each forbidding string consists of at most two symbols characterize the family of recursively enumerable languages. (2) GOFGs where the rules in one of the two sets of rules contain only ordinary context-free rules without any forbidding strings characterize the family of context-free languages. (3) GOFGs with the set of left forbidding rules coinciding with the set of right forbidding rules characterize the family of context-free languages.     

The language intersection problem for non-recursive context-free grammars

We prove that, given as input two context-free grammars, deciding non-emptiness of intersection of the two generated languages is PSPACE-complete if at least one grammar is non-recursive. The problem remains PSPACE-complete when both grammars are non-recursive and deterministic. Also investigated are generalizations of the problem to several context-free grammars, of which a certain number are non-recursive.     

Requirements for computational rule checking of requests for proposals (RFPs) for building designs in South Korea

This study reports on the requirements for developing computer-interpretable rules for checking the compliance of a building design in a request for proposal (RFP), especially in the building information modeling (BIM) environment. It focuses on RFPs for large public buildings (over 5 million dollars) in South Korea, which generally entail complex designs. A total of 27 RFPs for housing, office, exhibition, hospital, sports center, and courthouse projects were analyzed to develop computer-interpreted RFP rules. Each RFP was composed of over 1800 sentences. Of these, only three to 366 sentences could be translated into a computer-interpretable sentence. For further analysis, this study deployed context-free grammar (CFG) in natural language processing, and classified morphemes into four categories: i.e., object (noun), method (verb), strictness (modal), and others. The subcategorized morphemes included three types of objects, twenty-nine types of methods, and five levels of strictness. The coverage applicability of the derived objects and methods was checked and validated against three additional RFP cases and then through a test case using a newly developed model checker system. The findings are expected to be useful as a guideline and basic data for system developers in the development of a generalized automated design checking system for South Korea.     

Language Structure Using Fuzzy Similarity

Learning of (context-free) grammar rules that are based on alignment between texts of a given collection of sentences has attracted the attention of many researchers. We define and study the alignment profile and formulate fuzzy similarity of alignment profiles for a given collection of sentences. Using the fuzzy-similarity-based profile alignment, we give a methodology to formulate stochastic context-free grammar (CFG) rules. We introduce profile-alignment-based dynamic sentence similarity threshold to formulate the rules of stochastic CFG. The proposed methodology is tested using Child Language Data Exchange System (CHILDES) dataset of sentences. The benefits of our approach are experimentally demonstrated. Since our approach does not make use of any domain knowledge, it is expected to be useful in wide variety of applications requiring model construction.     

Linearity and nondeletion on monadic context-free tree grammars

In this paper, subclasses of monadic context-free tree grammars (CFTGs) are compared. Since linear, nondeleting, monadic CFTGs generate the same class of string languages as tree adjoining grammars (TAGs), it is examined whether the restrictions of linearity and nondeletion on monadic CFTGs are necessary to generate the same class of languages.