Theory of Logic Programming and the Semantics of Non-Monotonic Formal Grammars

In this dissertation we give the first proper mathemat-ical treatment of the semantics of Boolean grammars. We show that for every Boolean grammar there exists a distin-guished (three-valued) interpretation of the non-terminal symbols, which satisfies all the rules of the grammar and at the same time is the least fixed-point of an operator asso-ciated with the grammar. Then, we propose an O(n3) al-gorithm for parsing that applies to any normalized Boolean grammar. Finally, we give a purely game-theoretic charac-terization of Boolean grammars: we propose a two-player infinite game of perfect information for Boolean grammars, which is equivalent to their well-founded semantics. 1 Well-Founded Semantics for Boolean Grammars In this dissertation we propose and investigate the properties of the well-founded semantics for Boolean grammars. We begin by giving the formal definition of Boolean grammars. We then define the well-founded semantics of a given Boolean grammar as the least fixed-point of an operator associated with the grammar. Moreover we examine the mathematical properties of this operator in detail