Search results for "Rewriting"

Graph Rewriting Based Search for Molecular Structures: Definitions, Algorithms, Hardness

2018

We define a graph rewriting system that is easily understandable by humans, but rich enough to allow very general queries to molecule databases. It is based on the substitution of a single node in a node- and edge-labeled graph by an arbitrary graph, explicitly assigning new endpoints to the edges incident to the replaced node. For these graph rewriting systems, we are interested in the subgraph-matching problem. We show that the problem is NP-complete, even on graphs that are stars. As a positive result, we give an algorithm which is polynomial if both rules and query graph have bounded degree and bounded cut size. We demonstrate that molecular graphs of practically relevant molecules in d…

Il frammento riscritto. Su alcune citazioni tragiche ciceroniane

2016

The monody of Ennius'Andromacha represents for Cicero a poetic model and a source of inspiration. The quotations of the pro Sestio sound like imitation and rewriting

Context-free Languages

1988

In this chapter we shall define a class of rewriting systems called context-free grammars. The left-hand side of a rule in a context-free grammar consists of a single symbol, so that symbols are rewritten “context-freely”. Context-free grammars are of central importance to us because they define the class of context-free languages, the parsing of which is the subject of this book. In this chapter we shall consider some structural properties of context-free grammars which are of importance in parsing. Also, a basic method for recognizing context-free languages will be given.

Elements of Language Theory

1988

In this chapter we shall review the mathematical and computer science background on which the presentation in this book is based. We shall discuss the elements of discrete mathematics and formal language theory, emphasizing those issues that are of importance from the point of view of context-free parsing. We shall devote a considerable part of this chapter to matters such as random access machines and computational complexity. These will be relevant later when we derive efficient algorithms for parsing theoretic problems or prove lower bounds for the complexity of these problems. In this chapter we shall also discuss a general class of formal language descriptors called “rewriting systems”…

When can an equational simple graph be generated by hyperedge replacement?

1998

Infinite hypergraphs with sources arise as the canonical solutions of certain systems of recursive equations written with operations on hypergraphs. There are basically two different sets of such operations known from the literature, HR and VR. VR is strictly more powerful than HR on simple hypergraphs. Necessary conditions are known ensuring that a VR-equational simple hypergraph is also HR-equational. We prove that two of them, namely having finite tree-width or not containing the infinite bipartite graph, are also sufficient. This shows that equational hypergraphs behave like context-free sets of finite hypergraphs.

New ways of looking into handwritten miscellanies of the seventeenth century: the case of “Spes Altera”

2020

A large number of copies of Shakespeare’s Sonnet 2 circulated in handwritten miscellanies from the second quarter of the Seventeenth Century. Eleven of those copies have significant variant readings that have led critics to put forward different hypotheses regarding their nature and quality. Most critics, taking into account stylometric analyses, have regarded them as early drafts of Shakespeare’s printed version, and have agreed on their poor quality.By paying due attention to the text’s context of production and reception, we have reached a different conclusion regarding both the nature and quality of the handwritten versions of Sonnet 2. In our view, they are the product of a conscious r…

Renate Haas, ed. Rewriting Academia: The Development of the Anglicist Women’s and Gender Studies of Continental Europe. Frankfurt am Main: Peter Lang…

2017

A decidable word problem without equivalent canonical term rewriting system

1989

We present a weak associative single-axiom system having the following property: the word problem is decidable with an efficient algorithm even though there does not exist any finite equivalent canonical term rewriting system.

Incremental termination proofs and the length of derivations

1991

Incremental termination proofs, a concept similar to termination proofs by quasi-commuting orderings, are investigated. In particular, we show how an incremental termination proof for a term rewriting system T can be used to derive upper bounds on the length of derivations in T. A number of examples show that our results can be applied to yield (sharp) low-degree polynomial complexity bounds.

Termination of a set of rules modulo a set of equations

2006

The problem of termination of a set R of rules modulo a set E of equations, called E-termination problem, arises when trying to complete the set of rules in order to get a Church-Rosser property for the rules modulo the equations. We first show here that termination of the rewriting relation and E-termination are the same whenever the used rewriting relation is E-commuting, a property inspired from Peterson and Stickel’s E-compatibility property. More precisely, their results can be obtained by requiring termination of the rewriting relation instead of E-termination if E-commutation is used instead of E-compatibility. When the rewriting relation is not E-commuting, we show how to reduce E-t…