Locally stratified Boolean grammars
Saved in:
| Title: | Locally stratified Boolean grammars |
|---|---|
| Authors: | Nomikos, Christos1 cnomikos@cs.uoi.gr, Rondogiannis, Panos2 prondo@di.uoa.gr |
| Source: | Information & Computation. Sep2008, Vol. 206 Issue 9/10, p1219-1233. 15p. |
| Subjects: | Machine theory, Algorithms, Mathematical logic, Comparative linguistics |
| Abstract: | Abstract: We introduce locally stratified Boolean grammars, a natural subclass of Boolean grammars with many desirable properties. Informally, if a grammar is locally stratified then the set of all pairs of the form (nonterminal, string) of the grammar can be mapped to a (possibly infinite) set of strata so as that the following holds: if the membership of a string w in the language defined by nonterminal A depends on the membership of string in the language defined by nonterminal B, then (B,) cannot belong to a stratum higher than the stratum of (A,w); furthermore, if the above dependency is obtained through negation, () must belong to a stratum lower than the stratum of (A,w). We prove that local stratifiability can be tested in linear time with respect to the size of the given grammar. We then develop the semantics of locally stratified grammars and prove that it is independent of the choice of the stratification mapping. We argue that the class of locally stratified Boolean grammars appears at present to be the broadest subclass of Boolean grammars that can be given a classical semantics (ie., without resorting to three-valued formal language theory). [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: 34082520 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Locally stratified Boolean grammars – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Nomikos%2C+Christos%22">Nomikos, Christos</searchLink><relatesTo>1</relatesTo><i> cnomikos@cs.uoi.gr</i><br /><searchLink fieldCode="AR" term="%22Rondogiannis%2C+Panos%22">Rondogiannis, Panos</searchLink><relatesTo>2</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>. Sep2008, Vol. 206 Issue 9/10, p1219-1233. 15p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Machine+theory%22">Machine theory</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+logic%22">Mathematical logic</searchLink><br /><searchLink fieldCode="DE" term="%22Comparative+linguistics%22">Comparative linguistics</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Abstract: We introduce locally stratified Boolean grammars, a natural subclass of Boolean grammars with many desirable properties. Informally, if a grammar is locally stratified then the set of all pairs of the form (nonterminal, string) of the grammar can be mapped to a (possibly infinite) set of strata so as that the following holds: if the membership of a string w in the language defined by nonterminal A depends on the membership of string in the language defined by nonterminal B, then (B,) cannot belong to a stratum higher than the stratum of (A,w); furthermore, if the above dependency is obtained through negation, () must belong to a stratum lower than the stratum of (A,w). We prove that local stratifiability can be tested in linear time with respect to the size of the given grammar. We then develop the semantics of locally stratified grammars and prove that it is independent of the choice of the stratification mapping. We argue that the class of locally stratified Boolean grammars appears at present to be the broadest subclass of Boolean grammars that can be given a classical semantics (ie., without resorting to three-valued formal language theory). [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=34082520 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1016/j.ic.2008.03.022 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 15 StartPage: 1219 Subjects: – SubjectFull: Machine theory Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Mathematical logic Type: general – SubjectFull: Comparative linguistics Type: general Titles: – TitleFull: Locally stratified Boolean grammars Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Nomikos, Christos – PersonEntity: Name: NameFull: Rondogiannis, Panos IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 09 Text: Sep2008 Type: published Y: 2008 Identifiers: – Type: issn-print Value: 08905401 Numbering: – Type: volume Value: 206 – Type: issue Value: 9/10 Titles: – TitleFull: Information & Computation Type: main |
| ResultId | 1 |
