Back to search

National and Kapodistrian University of Athens

Εφαρμογή της θεωρίας του λογικού προγραμματισμου στη σημασιολογία των μη-μονοτονικών τυπικών γραμματικών

Abstract

dc:description

Boolean grammars [A. Okhotin, Information and Computation 194(1) (2004) 19-48] are a promising extension of context-free grammars that supports conjunction and negation in rule bodies. In this dissertation we give the first proper mathematical treatment of the semantics of Boolean grammars, i.e. a semantics that applies to all such grammars, independently of their syntax. The key idea of our proposal comes from the area of negation in logic programming, and in particular from the so-called well-founded semantics which is widely accepted in this area to be the “correct” approach to negation. We show that for every Boolean grammar there exists a distinguished (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 associated with the grammar. Then, we demonstrate that every Boolean grammar can be transformed into an equivalent (under the new semantics) grammar in normal form. Based on this normal form, we propose an Ο(n³) algorithm for parsing that applies to any such normalized Boolean grammar. In summary, the first contribution of this dissertation is to provide a semantics which applies to all Boolean grammars while at the same time retaining the complexity of parsing associated with this type of grammars. The second contribution of the dissertation is a purely game-theoretic characterization of Boolean grammars. In particular, we propose a two player infinite game of perfect information for Boolean grammars, which is equivalent to their well-founded semantics. The game is directly applicable to the simpler classes of conjunctive and context-free grammars, and it offers a promising new connection between game theory and formal languages.

Degree

thesis:*
Grantor dc:publisher
National and Kapodistrian University of Athens
Year dc:date
2009

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Kountouriotis, Vasileios
  • Κουντουριώτης, Βασίλειος

Subjects

dc:subject × 11

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/23946

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Kountouriotis, Vasileios; Κουντουριώτης, Βασίλειος. Εφαρμογή της θεωρίας του λογικού προγραμματισμου στη σημασιολογία των μη-μονοτονικών τυπικών γραμματικών. National and Kapodistrian University of Athens, 2009. http://hdl.handle.net/10442/hedi/23946