Two Forms of Dependence in Propositional Logic: Controllability and Definability
Abstract
We investigate two forms of dependence between variables and/or formulas within a propositional knowledge base: controllability (a set of variables X controls a formula ? if there is a way to fix the truth value of the variables in X in order to achieve ? to have a prescribed truth value) and definability (X defines a variable y if every truth assignment of the variables in X enables us finding out the truth value of y). Several characterization results are pointed out, complexity issues are analyzed, and some applications of both notions, including decision under incomplete knowledge and/or partial observability, and hypothesis discrimination, are sketched.
Cite
Text
Lang and Marquis. "Two Forms of Dependence in Propositional Logic: Controllability and Definability." AAAI Conference on Artificial Intelligence, 1998.Markdown
[Lang and Marquis. "Two Forms of Dependence in Propositional Logic: Controllability and Definability." AAAI Conference on Artificial Intelligence, 1998.](https://mlanthology.org/aaai/1998/lang1998aaai-two/)BibTeX
@inproceedings{lang1998aaai-two,
title = {{Two Forms of Dependence in Propositional Logic: Controllability and Definability}},
author = {Lang, Jérôme and Marquis, Pierre},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {1998},
pages = {268-273},
url = {https://mlanthology.org/aaai/1998/lang1998aaai-two/}
}