Deductive parsing of visual languages

Paolo Bottoni, Bernd Meyer, Kim Marriott, Francesco P Presicce

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    4 Citations (Scopus)


    Computational linguistics has largely focussed on written and spoken textual languages. However, humans use many other kinds of symbolic notations for communication, in particular, two-dimensional graphical notations such as mathematical notation, choreography notation, organizational charts and electrical circuit diagrams. We can term such multi-dimensional symbolic notations, visual languages. Like textual languages, many of these notations have a well defined syntax and semantics. The standard approach to computer interpretation of visual languages is to utilize parsing technologies based on multi-dimensional grammars. In this paper we investigate a new approach to parsing visual languages based on linear logic. The advantages of this logic-based approach are threefold: It provides a more adequate level for modelling the semantics of visual languages; it allows us to implement them based on automated deduction and it provides a good basis for the investigation of their formal properties. We show how attributed multiset grammars, one of the most widely used methods for multi-dimensional parsing, can be embedded into linear logic, demonstrate how parsing corresponds to linear proofs and prove the soundness and correctness of this embedding. Importantly, our embedding is into a subset of a linear logic programming language. Thus, we also demonstrate how multi-dimensional parsing can be implemented as a directly executable linear logic program.
    Original languageEnglish
    Title of host publicationLogical Aspects of Computational Linguistics
    Subtitle of host publication4th International Conference, LACL 2001 Le Croisic, France, June 27-29, 2001 Proceedings
    EditorsPhilippe de Groote, Glyn Morrill, Christian Retore
    Place of PublicationBerlin Germany
    Number of pages16
    ISBN (Print)3540422730
    Publication statusPublished - 2001
    EventInternational Conference on Logical Aspects of Computational Linguistics 2001 - Le Croisic, France
    Duration: 27 Jun 200129 Jun 2001
    Conference number: 4th (Proceedings)

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743


    ConferenceInternational Conference on Logical Aspects of Computational Linguistics 2001
    Abbreviated titleLACL 2001
    CityLe Croisic
    Internet address

    Cite this