Robustness of decentralized knowledge systems: a grammar-theoretic view

This paper introduces the formal framework of grammar systems to handle a practical and important property of decentralized rule-based knowledge systems. The property is called robustness. In our framework, a rule-based system is robust when some rules can be removed from it and yet its critical functionality remains unchanged. As a theoretical framework for study robustness of decentralized rule-based systems we use grammar systems. We prove within that framework that the question whether a knowledge system is robust or not is undecidable. In contrast, we prove with the same framework that whether or not a component is ever enabled, or whether or not a component working in a special—so called maximal—mode blocks the further functioningof a systems when enabled, are decidable. Some open problems are also formulated.