Results 1 to 10 of about 623,637 (299)
Complexity Analysis of Precedence Terminating Infinite Graph Rewrite Systems [PDF]
Electronic Proceedings in Theoretical Computer Science, 2015 The general form of safe recursion (or ramified recurrence) can be expressed by an infinite graph rewrite system including unfolding graph rewrite rules introduced by Dal Lago, Martini and Zorzi, in which the size of every normal form by innermost ...
Naohi Eguchi
doaj +8 more sources
The First-Order Theory of Ground Tree Rewrite Graphs [PDF]
Logical Methods in Computer Science, 2014 We prove that the complexity of the uniform first-order theory of ground tree rewrite graphs is in ATIME(2^{2^{poly(n)}},O(n)). Providing a matching lower bound, we show that there is some fixed ground tree rewrite graph whose first-order theory is hard ...
Stefan Göller, Markus Lohrey
doaj +6 more sources
Decreasing Diagrams for Confluence and Commutation [PDF]
Logical Methods in Computer Science, 2020 Like termination, confluence is a central property of rewrite systems. Unlike for termination, however, there exists no known complexity hierarchy for confluence.
Jörg Endrullis +2 more
doaj +4 more sources
Pattern graph rewrite systems [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 String diagrams are a powerful tool for reasoning about physical processes, logic circuits, tensor networks, and many other compositional structures. Dixon, Duncan and Kissinger introduced string graphs, which are a combinatoric representations of string
Aleks Kissinger +2 more
doaj +3 more sources
Extending Context-Sensitivity in Term Rewriting [PDF]
Electronic Proceedings in Theoretical Computer Science, 2010 We propose a generalized version of context-sensitivity in term rewriting based on the notion of "forbidden patterns". The basic idea is that a rewrite step should be forbidden if the redex to be contracted has a certain shape and appears in a certain ...
Bernhard Gramlich, Felix Schernhammer
doaj +8 more sources
Linear Compressed Pattern Matching for Polynomial Rewriting (Extended Abstract) [PDF]
Electronic Proceedings in Theoretical Computer Science, 2013 This paper is an extended abstract of an analysis of term rewriting where the terms in the rewrite rules as well as the term to be rewritten are compressed by a singleton tree grammar (STG).
Manfred Schmidt-Schauss
doaj +4 more sources
On Constructor Rewrite Systems and the Lambda Calculus [PDF]
Logical Methods in Computer Science, 2012 We prove that orthogonal constructor term rewrite systems and lambda-calculus with weak (i.e., no reduction is allowed under the scope of a lambda-abstraction) call-by-value reduction can simulate each other with a linear overhead.
Ugo Dal Lago, Simone Martini
doaj +4 more sources
Loops under Strategies ... Continued [PDF]
Electronic Proceedings in Theoretical Computer Science, 2010 While there are many approaches for automatically proving termination of term rewrite systems, up to now there exist only few techniques to disprove their termination automatically. Almost all of these techniques try to find loops, where the existence of
René Thiemann +3 more
doaj +4 more sources
Deciding Confluence and Normal Form Properties of Ground Term Rewrite Systems Efficiently [PDF]
Logical Methods in Computer Science, 2018 It is known that the first-order theory of rewriting is decidable for ground term rewrite systems, but the general technique uses tree automata and often takes exponential time.
Bertram Felgenhauer
doaj +3 more sources
Logical Methods in Computer Science, 2013 This paper is concerned with the complexity analysis of constructor term rewrite systems and its ramification in implicit computational complexity. We introduce a path order with multiset status, the polynomial path order POP*, that is applicable in two ...
Martin Avanzini, Georg Moser
doaj +3 more sources