View in EDS

Well-founded semantics for Boolean grammars

Saved in:
Bibliographic Details
Title: Well-founded semantics for Boolean grammars
Authors: Kountouriotis, Vassilis1 bk@di.uoa.gr, Nomikos, Christos2 cnomikos@cs.uoi.gr, Rondogiannis, Panos1 prondo@di.uoa.gr
Source: Information & Computation. Sep2009, Vol. 207 Issue 9, p945-967. 23p.
Subjects: Programming language semantics, Boolean algebra, Logic programming, Computational complexity, Fixed point theory
Abstract: 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 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. [Copyright &y& Elsevier]
Copyright of Information & Computation is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 43621915
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Well-founded semantics for Boolean grammars
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Kountouriotis%2C+Vassilis%22">Kountouriotis, Vassilis</searchLink><relatesTo>1</relatesTo><i> bk@di.uoa.gr</i><br /><searchLink fieldCode="AR" term="%22Nomikos%2C+Christos%22">Nomikos, Christos</searchLink><relatesTo>2</relatesTo><i> cnomikos@cs.uoi.gr</i><br /><searchLink fieldCode="AR" term="%22Rondogiannis%2C+Panos%22">Rondogiannis, Panos</searchLink><relatesTo>1</relatesTo><i> prondo@di.uoa.gr</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Information+%26+Computation%22">Information & Computation</searchLink>. Sep2009, Vol. 207 Issue 9, p945-967. 23p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Programming+language+semantics%22">Programming language semantics</searchLink><br /><searchLink fieldCode="DE" term="%22Boolean+algebra%22">Boolean algebra</searchLink><br /><searchLink fieldCode="DE" term="%22Logic+programming%22">Logic programming</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Fixed+point+theory%22">Fixed point theory</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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 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. [Copyright &y& Elsevier]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Information & Computation is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=43621915
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.ic.2009.05.002
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 23
        StartPage: 945
    Subjects:
      – SubjectFull: Programming language semantics
        Type: general
      – SubjectFull: Boolean algebra
        Type: general
      – SubjectFull: Logic programming
        Type: general
      – SubjectFull: Computational complexity
        Type: general
      – SubjectFull: Fixed point theory
        Type: general
    Titles:
      – TitleFull: Well-founded semantics for Boolean grammars
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Kountouriotis, Vassilis
      – PersonEntity:
          Name:
            NameFull: Nomikos, Christos
      – PersonEntity:
          Name:
            NameFull: Rondogiannis, Panos
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 09
              Text: Sep2009
              Type: published
              Y: 2009
          Identifiers:
            – Type: issn-print
              Value: 08905401
          Numbering:
            – Type: volume
              Value: 207
            – Type: issue
              Value: 9
          Titles:
            – TitleFull: Information & Computation
              Type: main
ResultId 1