A Superposition-Based Calculus for Diagrammatic Reasoning

International audienceWe introduce a class of rooted graphs which are expressive enough to encode various kinds of classical or quantum circuits. We then follow a set-theoretic approach to define rewrite systems over the considered graphs. Afterwards, we tackle the problem of equational reasoning with the graphs under study and we propose a new Superposition calculus to check the unsatisfiability of formulas consisting of equations or disequations over these graphs. We establish the soundness and refutational completeness of the calculus. CCS CONCEPTS • Theory of computation → Automated reasoning; Equational logic and rewriting