Publications related to Semi-Thue system

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

We present a quasilinear time algorithm to decide the word problem on a natural algebraic structures we call orthocomplemented bisemilattices, a subtheory of boolean algebra. We use as a base a variation of Hopcroft, Ullman and Aho algorithm for tree isomo ...

Springer2022

Structural Rewriting in XOR-Majority Graphs

Giovanni De Micheli, Mathias Soeken, Zhufei Chu

In this paper, we present a structural rewriting method for a recently proposed XOR-Majority graph (XMG), which has exclusive-OR (XOR), majority-of-three (MAJ), and inverters as primitives. XMGs are an extension of Majority-Inverter Graphs (MIGs). Previous ...

ASSOC COMPUTING MACHINERY2019

Busy Man’s Synthesis: Combinational Delay Optimization With SAT

Giovanni De Micheli, Mathias Soeken

Boolean SAT solving can be used to find a minimum- size logic network for a given small Boolean function. This paper extends the SAT formulation to find a minimum-size network under delay constraints. Delay constraints are given in terms of input arrival t ...

Ieee2017

A Novel Basis for Logic Rewriting

Giovanni De Micheli, Mathias Soeken, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù, Winston Jason Haaswijk

Given a set of logic primitives and a Boolean function, exact synthesis finds the optimum representation (e.g., depth or size) of the function in terms of the primitives. Due to its high computational complexity, the use of exact synthesis is limite ...

Ieee2017

Quoted Staged Rewriting: A Practical Approach to Library-Defined Optimizations

Christoph Koch, Amir Shaikhha, Lionel Emile Vincent Parreaux

Staging has proved a successful technique for programmatically removing code abstractions, thereby allowing for faster program execution while retaining a high-level interface for the programmer. Unfortunately, techniques based on staging suffer from a num ...

ACM2017

Moment Semantics for Reversible Rule-Based Systems

Sandro Stucki

We develop a notion of stochastic rewriting over marked graphs – i.e. directed multigraphs with degree constraints. The approach is based on double-pushout (DPO) graph rewriting. Marked graphs are expressive enough to internalize the ‘no-dangling-edge’ con ...

Springer International Publishing2015

A Decision Procedure for (Co)datatypes in SMT Solvers

Andrew Joseph Reynolds

We present a decision procedure that combines reasoning about datatypes and codatatypes. The dual of the acyclicity rule for datatypes is a uniqueness rule that identifies observationally equal codatatype values, including cyclic values. The procedure deci ...

Springer-Verlag Berlin2015

Spiral in Scala: Towards the Systematic Construction of Generators for Performance Libraries

Martin Odersky, Tiark Rompf, Alen Stojanov

Program generators for high performance libraries are an appealing solution to the recurring problem of porting and optimizing code with every new processor generation, but only few such generators exist to date. This is due to not only the difficulty of t ...

Assoc Computing Machinery2014

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Semi-Thue system

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Structural Rewriting in XOR-Majority Graphs

Busy Man’s Synthesis: Combinational Delay Optimization With SAT

A Novel Basis for Logic Rewriting

Quoted Staged Rewriting: A Practical Approach to Library-Defined Optimizations

Moment Semantics for Reversible Rule-Based Systems

A Decision Procedure for (Co)datatypes in SMT Solvers

Additional Material for "Unifying Data Representation Transformations"

Spiral in Scala: Towards the Systematic Construction of Generators for Performance Libraries

Functional Nets

Graph Chatbot

Chat with Graph Search

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Quoted Staged Rewriting: A Practical Approach to Library-Defined Optimizations

Additional Material for "Unifying Data Representation Transformations"

Structural Rewriting in XOR-Majority Graphs

A Novel Basis for Logic Rewriting

Busy Man’s Synthesis: Combinational Delay Optimization With SAT

Moment Semantics for Reversible Rule-Based Systems

Spiral in Scala: Towards the Systematic Construction of Generators for Performance Libraries

Functional Nets

A Decision Procedure for (Co)datatypes in SMT Solvers