首页 | 本学科首页   官方微博 | 高级检索  
     检索      


On decidability of the decomposability problem for finite theories
Authors:Andrey S Morozov  Denis K Ponomaryov
Institution:1.Sobolev Institute of Mathematics,Novosibirsk,Russia;2.Institute of Informatics Systems,Novosibirsk,Russia
Abstract:We consider the decomposability problem for elementary theories, i.e. the problem of deciding whether a theory has a nontrivial representation as a union of two (or several) theories in disjoint signatures. For finite universal Horn theories, we prove that the decomposability problem is $ \sum _1^0 $ \sum _1^0 -complete and, thus, undecidable. We also demonstrate that the decomposability problem is decidable for finite theories in signatures consisting only of monadic predicates and constants.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号