Revistes Publicacions URV: Triangle - llenguatge, literatura, computació> 2012

Owicki-Gries Theory: A Possible Way of Relating Grammar Systems to Concurrent Programs

  • Datos identificativos

    Identificador: RP:4406
    Handle: https://hdl.handle.net/20.500.11797/RP4406
    Autores:
    Grando, María Adela
    Resumen:
    The aim of this paper is to show how grammar systems and concurrent programs might be viewed as related models for distributed and cooperating computation. We argue that it is possible to translate a grammar system into a concurrent program, where the Owicki-Gries theory and other tools available in the programming framework can be used. The converse translation is also possible and this turns out to be useful when we are looking for a grammar system that can generate a given language. In order to show this we use tools from concurrent programming theory to prove that Lcd = {anbmcndm | n,m ≥ 1} can be generated by a non-returning Parallel Communicating grammar system with three regular components. We show that this strategy can be helpful in the construction of grammar systems that generate strings in less time and more eciently. We also discuss the absence of strategies in the concurrent programming theory to prove that Lcd can be generated by any Parallel Communicating grammar system with two regular components.

  • Otros:

    Autor según el artículo: Grando, María Adela
    Palabras clave: language
    Resumen: The aim of this paper is to show how grammar systems and concurrent programs might be viewed as related models for distributed and cooperating computation. We argue that it is possible to translate a grammar system into a concurrent program, where the Owicki-Gries theory and other tools available in the programming framework can be used. The converse translation is also possible and this turns out to be useful when we are looking for a grammar system that can generate a given language. In order to show this we use tools from concurrent programming theory to prove that Lcd = {anbmcndm | n,m ≥ 1} can be generated by a non-returning Parallel Communicating grammar system with three regular components. We show that this strategy can be helpful in the construction of grammar systems that generate strings in less time and more eciently. We also discuss the absence of strategies in the concurrent programming theory to prove that Lcd can be generated by any Parallel Communicating grammar system with two regular components.
    Año de publicación de la revista: 2012
    Tipo de publicación: info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article