Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/11014Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Kountouriotis, V. | en |
| dc.contributor.author | Nomikos, C. | en |
| dc.contributor.author | Rondogiannis, P. | en |
| dc.date.accessioned | 2015-11-24T17:02:07Z | - |
| dc.date.available | 2015-11-24T17:02:07Z | - |
| dc.identifier.issn | 0890-5401 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/11014 | - |
| dc.rights | Default Licence | - |
| dc.title | Well-founded semantics for Boolean grammars | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.identifier.primary | Doi 10.1016/J.Ic.2009.05.002 | - |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 2009 | - |
| heal.abstract | Boolean grammars [A. Okhotin, Boolean grammars, 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 paper, we give a novel semantics for Boolean grammars which 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 O(n(3)) algorithm for parsing that applies to any such normalized Boolean grammar. In summary, the main contribution of this paper 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. (c) 2009 Elsevier Inc. All rights reserved. | en |
| heal.journalName | Information and Computation | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Kountouriotis-2009-Well-founded semanti.pdf | 379.83 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
