A GLR-like Parsing Algorithm for Three-Valued Interpretations of Boolean Grammars with Strong Negation
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929496323522560 |
|---|---|
| author | Adrián, Patrik Vaszil, György |
| author_facet | Adrián, Patrik Vaszil, György |
| contents | Boolean grammars generalize context-free rewriting by extending the possibilities when dealing with different rules for the same nonterminal symbol. By allowing not only disjunction (as in the case of usual context-free grammars), but also conjunction and negation as possible connections between different rules with the same left-hand side, they are able to simplify the description of context-free languages and characterize languages that are not context-free. The use of negation, however, leads to the possibility of introducing rules that interplay in such a way which is problematic to handle in the classical, two-valued logical setting. Here we define a three valued interpretation to deal with such contradictory grammars using a method introduced originally in the context of logic programming, and present an algorithm to determine the membership status of strings with respect to the resulting three valued languages. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06966 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A GLR-like Parsing Algorithm for Three-Valued Interpretations of Boolean Grammars with Strong Negation Adrián, Patrik Vaszil, György Formal Languages and Automata Theory Logic in Computer Science Boolean grammars generalize context-free rewriting by extending the possibilities when dealing with different rules for the same nonterminal symbol. By allowing not only disjunction (as in the case of usual context-free grammars), but also conjunction and negation as possible connections between different rules with the same left-hand side, they are able to simplify the description of context-free languages and characterize languages that are not context-free. The use of negation, however, leads to the possibility of introducing rules that interplay in such a way which is problematic to handle in the classical, two-valued logical setting. Here we define a three valued interpretation to deal with such contradictory grammars using a method introduced originally in the context of logic programming, and present an algorithm to determine the membership status of strings with respect to the resulting three valued languages. |
| title | A GLR-like Parsing Algorithm for Three-Valued Interpretations of Boolean Grammars with Strong Negation |
| topic | Formal Languages and Automata Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2409.06966 |