Satisfiability of algebraic circuits over sets of natural numbers

DOI10.1016/J.DAM.2010.04.001zbMATH Open1194.94206OpenAlexW1967161325MaRDI QIDQ987688FDOQ987688

Authors: Christian Glaßer, Christian Reitwießner, Stephen Travers, Matthias Waldherr 

Publication date: 13 August 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.04.001

Recommendations

• Satisfiability of Algebraic Circuits over Sets of Natural Numbers
• Equivalence Problems for Circuits over Sets of Natural Numbers
• Equivalence problems for circuits over sets of natural numbers
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• The complexity of membership problems for circuits over sets of natural numbers
• scientific article; zbMATH DE number 1962845
• Computational completeness of equations over sets of natural numbers
• On the Computational Completeness of Equations over Sets of Natural Numbers
• Publication:4729350

zbMATH Keywords

computational complexitysatisfiability problemscombinatorial integer circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analytic circuit theory (94C05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The decision problem for exponential diophantine equations
• PRIMES is in P
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Equivalence Problems for Circuits over Sets of Natural Numbers
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (13)

• Parsing Boolean grammars over a one-letter alphabet using online convolution
• Expressive power, satisfiability and equivalence of circuits over nilpotent algebras
• Satisfiability of Algebraic Circuits over Sets of Natural Numbers
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Satisfiability in multi-valued circuits
• Balance problems for integer circuits
• Balance problems for integer circuits
• Complex algebras of arithmetic
• Computational completeness of equations over sets of natural numbers
• Emptiness problems for integer circuits
• Emptiness problems for integer circuits
• Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems

This page was built for publication: Satisfiability of algebraic circuits over sets of natural numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987688)