Incremental reasoning on monadic second-order logics with logic programming

Abstract

Data streams occur widely in various real world applications. The research on streaming data mainly focuses on the data management, query evaluation and optimization on data, but the work on incremental reasoning procedures for streaming knowledge bases is very limited. Typically reasoning services on large knowledge bases are very expensive, and need to be applied continuously when the data is received as a stream. Hence new techniques for optimizing this continuous process is needed for developing efficient reasoners on streaming data. In this paper, we describe a solution to an incremental reasoning problem on an expressive logic, namely monadic second-order logic, and point out further research directions in this area.