DIFFERENCE

We propose to revisit classical mathematical logic, computability and complexity theory using discrete ordinary differential equations (dODEs), sometime also called finite differences. We recently demonstrated that dODEs provide a novel and original approach between the classical world of computer science dealing with discrete objects (words, bytes, etc) and the continuous world of classical ordinary differential equations. We propose concretely: to characterize in a machine indepedent way main classes of complexity theory, extend the framework to deal with more general structures and more general equations than ordinary differential equations, relate the approach to classical approaches in logic, and devise applications with respect to the classification of hardness of problems in verification, and of the complexity of models coming from bioinformatics. Included experts come from complexity theory, logic, constraints solving, verification, computera algebra, bioinformatics.