A GLR-like Parsing Algorithm for Three-Valued Interpretations of Boolean Grammars with Strong Negation
<|reference_start|>A GLR-like Parsing Algorithm for Three-Valued Interpretations of Boolean Grammars with Strong Negation: 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.<|reference_end|>
@article{adrián2024a,
    title={A GLR-like Parsing Algorithm for Three-Valued Interpretations of Boolean
  Grammars with Strong Negation},
    author={Patrik Adri'an (University of Debrecen, Faculty of Informatics),
  Gy"orgy Vaszil (University of Debrecen, Faculty of Informatics)},
    journal={EPTCS 407, 2024, pp. 27-43},
    year={2024},
    doi={10.4204/EPTCS.407.3},
    archivePrefix={arXiv},
    eprint={2409.06966},
    primaryClass={cs.FL cs.LO}
}