Results 11 to 20 of about 836,741 (199)
Soundness of Unravelings for Conditional Term Rewriting Systems via Ultra-Properties Related to Linearity [PDF]
Logical Methods in Computer Science, 2012 Unravelings are transformations from a conditional term rewriting system (CTRS, for short) over an original signature into an unconditional term rewriting systems (TRS, for short) over an extended signature. They are not sound w.r.t.
Naoki Nishida +2 more
doaj +1 more source
Consistency and Completeness of Rewriting in the Calculus of Constructions [PDF]
Logical Methods in Computer Science, 2008 Adding rewriting to a proof assistant based on the Curry-Howard isomorphism, such as Coq, may greatly improve usability of the tool. Unfortunately adding an arbitrary set of rewrite rules may render the underlying formal system undecidable and ...
Daria Walukiewicz-Chrzaszcz +1 more
doaj +1 more source
Infinitary Combinatory Reduction Systems: Confluence [PDF]
Logical Methods in Computer Science, 2009 We study confluence in the setting of higher-order infinitary rewriting, in particular for infinitary Combinatory Reduction Systems (iCRSs). We prove that fully-extended, orthogonal iCRSs are confluent modulo identification of hypercollapsing subterms ...
Jeroen Ketema, Jakob Grue Simonsen
doaj +1 more source
Modularity of Convergence and Strong Convergence in Infinitary Rewriting [PDF]
Logical Methods in Computer Science, 2010 Properties of Term Rewriting Systems are called modular iff they are preserved under (and reflected by) disjoint union, i.e. when combining two Term Rewriting Systems with disjoint signatures.
Stefan Michael Kahrs
doaj +1 more source
Pushing for weighted tree automata [PDF]
Logical Methods in Computer Science, 2018 A weight normalization procedure, commonly called pushing, is introduced for weighted tree automata (wta) over commutative semifields. The normalization preserves the recognized weighted tree language even for nondeterministic wta, but it is most useful ...
Thomas Hanneforth +2 more
doaj +1 more source
Reachability Analysis of Innermost Rewriting [PDF]
Logical Methods in Computer Science, 2017 We consider the problem of inferring a grammar describing the output of a functional program given a grammar describing its input. Solutions to this problem are helpful for detecting bugs or proving safety properties of functional programs, and several ...
Thomas Genet, Yann Salmon
doaj +1 more source
Lineal: A linear-algebraic Lambda-calculus [PDF]
Logical Methods in Computer Science, 2017 We provide a computational definition of the notions of vector space and bilinear functions. We use this result to introduce a minimal language combining higher-order computation and linear algebra.
Pablo Arrighi, Gilles Dowek
doaj +1 more source
Bisimilarity on Basic Process Algebra is in 2-ExpTime (an explicit proof) [PDF]
Logical Methods in Computer Science, 2013 Burkart, Caucal, Steffen (1995) showed a procedure deciding bisimulation equivalence of processes in Basic Process Algebra (BPA), i.e. of sequential processes generated by context-free grammars.
Petr Jancar
doaj +1 more source
A Reduction-Preserving Completion for Proving Confluence of Non-Terminating Term Rewriting Systems [PDF]
Logical Methods in Computer Science, 2012 We give a method to prove confluence of term rewriting systems that contain non-terminating rewrite rules such as commutativity and associativity.
Takahito Aoto, Yoshihito Toyama
doaj +1 more source
Modes of Convergence for Term Graph Rewriting [PDF]
Logical Methods in Computer Science, 2012 Term graph rewriting provides a simple mechanism to finitely represent restricted forms of infinitary term rewriting. The correspondence between infinitary term rewriting and term graph rewriting has been studied to some extent.
Patrick Bahr
doaj +1 more source