We consider the reasoning problem of logical consequence between simple statements about the behaviour of continuous functions on certain intervals, representing the way that variables influence each other. Automated reasoning for such statements has applications in formal modelling of classroom experiments in natural sciences. A previous attempt, employing a simple proof system for this reasoning task, is known to be incomplete and unlikely to be extendable to obtain completeness for arbitrary experiments. Here we develop an algebraic approach in the form of an abstraction of the uncountable space of finite collections of continuous, real-valued functions, connected by a composition principle, into finitely many representatives of equivalence classes. We show that this is sufficient for the reasoning task at hand. The approach achieves completeness under very reasonable restrictions of the involved statements, extending what has previously been achieved using proof-theoretic means, and yields an upper bound of coNP.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Finite Abstraction of Real-Valued Functions for Complete Reasoning About Influence

  • Sören Möller,
  • Florian Bruse,
  • Martin Lange

摘要

We consider the reasoning problem of logical consequence between simple statements about the behaviour of continuous functions on certain intervals, representing the way that variables influence each other. Automated reasoning for such statements has applications in formal modelling of classroom experiments in natural sciences. A previous attempt, employing a simple proof system for this reasoning task, is known to be incomplete and unlikely to be extendable to obtain completeness for arbitrary experiments. Here we develop an algebraic approach in the form of an abstraction of the uncountable space of finite collections of continuous, real-valued functions, connected by a composition principle, into finitely many representatives of equivalence classes. We show that this is sufficient for the reasoning task at hand. The approach achieves completeness under very reasonable restrictions of the involved statements, extending what has previously been achieved using proof-theoretic means, and yields an upper bound of coNP.