Context-free grammars with selective rewriting

Summary Selective substitution grammars first introduced by Rozenberg are further investigated. In particular we study context-free grammars with selection, since the original model is too general in its generative power. It is shown how the families of context-free, EOL and ETOL languages can be characterized by selective context-free grammars. Further the effect of linguistic restrictions on the family of selection languages is investigated. Finally, the notion of a universal grammar is investigated in this framework, demonstrating the existence of selection universal grammars under weak conditions on the selection family.Work supported partially by a Natural Sciences and Engineering Research Council of Canada grant No. A-7700 and partially by the Universitaire Instelling Antwerpen     

SaBRe: load-time selective binary rewriting

Binary rewriting consists in disassembling a program to modify its instructions. However, existing solutions suffer from shortcomings in terms of soundness and performance. We present SaBRe, a load-time system for selective binary rewriting. SaBRe rewrites specific constructs—particularly system calls and functions—when the program is loaded into memory, and intercepts them using plugins through a simple API. We also discuss the theoretical underpinnings of disassembling and rewriting. We developed two backends—for x86_64 and RISC-V—which were used to implement three plugins: a fast system call tracer, a multi-version executor, and a fault injector. Our evaluation shows that SaBRe imposes little overhead, typically below 3%.

     

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.     

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.     

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.     

Nominal rewriting

Nominal rewriting is based on the observation that if we add support for α-equivalence to first-order syntax using the nominal-set approach, then systems with binding, including higher-order reduction schemes such as λ-calculus beta-reduction, can be smoothly represented. Nominal rewriting maintains a strict distinction between variables of the object-language (atoms) and of the meta-language (variables or unknowns). Atoms may be bound by a special abstraction operation, but variables cannot be bound, giving the framework a pronounced first-order character, since substitution of terms for variables is not capture-avoiding. We show how good properties of first-order rewriting survive the extension, by giving an efficient rewriting algorithm, a critical pair lemma, and a confluence theorem for orthogonal systems.     

Context-free languages over infinite alphabets

In this paper we introduce context-free grammars and pushdown automata over infinite alphabets. It is shown that a language is generated by a context-free grammar over an infinite alphabet if and only if it is accepted by a pushdown automaton over an infinite alphabet. Also the generated (accepted) languages possess many of the properties of the ordinary context-free languages: decidability, closure properties, etc.. This provides a substantial evidence for considering context-free grammars and pushdown automata over infinite alphabets as a natural extension of the classical ones. Received November 27, 1995 / March 4, 1997     

量化上下文无关语言的代数性质

通过引入量化下推自动机与量化上下文无关文法的定义,研究了以两种不同方式接受语言的量化下推自动机等价性问题,证明了在可交换的双幺赋值幺半群上,量化下推自动机接受的语言与量化上下文无关文法生成的语言相同。     

Context-free graph grammars and concatenation of graphs

An operation of concatenation is defined for graphs. This allows strings to be viewed as expressions denoting graphs, and string languages to be interpreted as graph languages. For a class of string languages, is the class of all graph languages that are interpretations of languages from . For the classes REG and LIN of regular and linear context-free languages, respectively, . is the smallest class of graph languages containing all singletons and closed under union, concatenation and star (of graph languages). equals the class of graph languages generated by linear HR (= Hyperedge Replacement) grammars, and is generated by the corresponding -controlled grammars. Two characterizations are given of the largest class such that . For the class CF of context-free languages, lies properly inbetween and the class of graph languages generated by HR grammars. The concatenation operation on graphs combines nicely with the sum operation on graphs. The class of context-free (or equational) graph languages, with respect to these two operations, is the class of graph languages generated by HR grammars. Received 16 October 1995 / 18 September 1996     

Scattered versus context-sensitive rewriting

Summary We study the relationship between scattered and context-sensitive rewriting. We prove that an extended version of scattered grammars produces exactly the context-sensitive languages. Also unordered scattered context languages are a proper subset of scattered context languages, and unordered scattered rewriting with erasing does not generate all scattered context (and thus not all context-sensitive) languages.Part of this research was done while this author visited the Hebrew University and was supported by the Leibniz Center     

Permutative rewriting and unification

Permutative rewriting provides a way of analyzing deduction modulo a theory defined by leaf-permutative equations. Our analysis naturally leads to the definition of the class of unify-stable axiom sets, in order to enforce a simple reduction strategy. We then give a uniform unification algorithm modulo theories E axiomatized this way. We prove that it computes complete sets of unifiers of simply exponential cardinality, and that the E-unification decision problem belongs to NP.     

Completeness of context-sensitive rewriting

Restrictions of rewriting may turn normal forms of some terms unreachable, leading to incomplete computations. Context-sensitive rewriting (csr) is the restriction of rewriting that only permits reductions on arguments selected by a replacement map μ  , which associates a subset μ(f)$\mu (f)$ of argument indices with each function symbol f. Hendrix and Meseguer defined an algebraic semantics for Term Rewriting Systems (TRSs) executing csr that can be used to reason about programs written in programming languages like CafeOBJ and Maude, where such replacement restrictions can be specified in programs. Semantic completeness of csr was also defined. In this paper we show that canonical replacement maps, which play a prominent role in simulating rewriting computations with csr, are necessary for completeness in important classes of TRSs.     

Priorities on context conditions in rewriting systems

This paper is concerned with letter-rewriting systems in which context-free rewriting productions are equipped with context conditions. Such a production, π = A → α can be used to rewrite an occurrence of A in a string x only if x satisfies the context conditions attached to π. In particular, we are concerned with situations where the context conditions of several productions are satisfied by a given occurrence of A. Deciding which of these productions can be applied to rewrite this occurrence is done by (once a priori) fixed priorities among all context conditions.     

Complete involutive rewriting systems

Given a monoid string rewriting system M, one way of obtaining a complete rewriting system for M is to use the classical Knuth–Bendix critical pairs completion algorithm. It is well-known that this algorithm is equivalent to computing a noncommutative Gröbner basis for M. This article develops an alternative approach, using noncommutative involutive basis methods to obtain a complete involutive rewriting system for M.     

上下文无关语言的可重复序列及其性质

通过分析下推自动机的运行规律和特点,提出上下文无关语言的可重复序列的概念,将其划分为平衡重复序列、增重复序列、减重复序列三类;研究了这三类可重复序列在下推自动机的状态转换图中的结构表现和性质,通过分析下推自动机状态转换图中标注回路与可重复序列之间的关系,给出求解可重复序列的计算方法;证明了不同类型的可重复序列对上下文无关语言性质的影响,利用可重复序列揭示了上下文无关语言的Pumping引理的本质特征,并给出正规语言判定的一个充分必要条件.     

Context-free attentional operators: The generalized symmetry transform

Active vision systems, and especially foveated vision systems, depend on efficient attentional mechanisms. We propose that machine visual attention should consist of both high-level, context-dependent components, and low-level, context free components. As a basis for the context-free component, we present an attention operator based on the intuitive notion of symmetry, which generalized many of the existing methods of detecting regions of interest. It is a low-level operator that can be applied successfully without a priori knowledge of the world. The resultingsymmetry edge map can be applied in various low, intermediate-and high- level tasks, such as extraction of interest points, grouping, and object recognition. In particular, we have implemented an algorithm that locates interest points in real time, and can be incorporated in active and purposive vision systems. The results agree with some psychophysical findings concerning symmetry as well as evidence concerning selection of fixation points. We demonstrate the performance of the transform on natural, cluttered images.