Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/10987Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Nomikos, C. | en |
| dc.contributor.author | Rondogiannis, P. | en |
| dc.date.accessioned | 2015-11-24T17:01:51Z | - |
| dc.date.available | 2015-11-24T17:01:51Z | - |
| dc.identifier.issn | 0890-5401 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/10987 | - |
| dc.rights | Default Licence | - |
| dc.title | Locally stratified Boolean grammars | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.identifier.primary | Doi 10.1016/J.Ic.2008.03.022 | - |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 2008 | - |
| heal.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 w' in the language defined by nonterminal B, then (B,w') cannot belong to a stratum higher than the stratum of (A,w); furthermore, if the above dependency is obtained through negation, (B,w') 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 (i.e., without resorting to three-valued formal language theory). (C) 2008 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 | |
|---|---|---|---|---|
| Nomikos-2008-Locally stratified B.pdf | 236.86 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
