Closure Properties of Ordered Languages.
Henning Fernau · 1996
. In this note, we solve questions regarding closure properties of ordered languages. Especially, ordered languages form a full abstract family of recursive languages which is neither intersection- nor complementationclosed. 1 Introduction and Definitions Ordered languages (or equivalently, forbidden random context languages) were introduced by Fris in 1968 [4]. Therefore, they belong to the classic topics of formal language theory. Surprisingly, several points on closure properties of the corresponding language families were marked as open in the monograph [3]. Most of these questions are solved in this note. We presuppose some knowledge of formal language theory on side of the reader. Especially, the Chomsky hierarchy L(CF) ( L(CS) ( L(REC) ( L(RE) should be known. An ordered grammar is a quintuple G = (VN ; V T ; P; S; OE), where VN , V T , P , and S 2 VN are the nonterminal alphabet, terminal alphabet, set of context-free productions, and axiom, respectively. OE is a partial ord...