Publication:
Synchronous set relations in rewriting logic

Thumbnail Image
Files

Files

Synchronous set relations in rewriting logic.pdf (413.59 KB)
View Statistics
Reference Managers
Mendeley
Indexers
Google Scholar CORE
QR Code
QR Code
Authors

Authors

Muñoz, César
Rocha Niño, Hernán Camilo
Abstract (Spanish)
Este artículo presenta una base matemática y una infraestructura lógica de reescritura para la ejecución y verificación de propiedades de relaciones de conjuntos sincrónicos. El fundamento matemático se da en el lenguaje de las relaciones abstractas de conjuntos. La infraestructura, que está escrita en el sistema Maude, permite la ejecución sincrónica de una relación establecida proporcionada por el usuario. Mediante el uso de la infraestructura, las técnicas de verificación de algoritmos, como el análisis de accesibilidad y la verificación de modelos, ya disponibles en Maude para la reescritura asincrónica tradicional, están disponibles automáticamente para la reescritura sincrónica de conjuntos. De esta manera, los lenguajes y sistemas sincrónicos basados ​​en conjuntos, como los construidos a partir de agentes, componentes u objetos, pueden especificarse y simularse de forma natural, y también son susceptibles de verificación formal en el sistema Maude. El uso de la infraestructura y algunas de sus capacidades de verificación basadas en Maude se ilustran con una semántica operativa ejecutable del lenguaje de intercambio de ejecución del plan (PLEXIL), un lenguaje síncrono desarrollado por la NASA para respaldar las operaciones de naves espaciales autónomas.
Abstract (English)
This paper presents a mathematical foundation and a rewriting logic infrastructure for the execution and property verification of synchronous set relations. The mathematical foundation is given in the language of abstract set relations. The infrastructure, which is written in the Maude system, enables the synchronous execution of a set relation provided by the user. By using the infrastructure, algorithm verification techniques such as reachability analysis and model checking, already available in Maude for traditional asynchronous rewriting, are automatically available to synchronous set rewriting. In this way, set-based synchronous languages and systems such as those built from agents, components, or objects can be naturally specified and simulated, and are also amenable to formal verification in the Maude system. The use of the infrastructure and some of its Maude-based verification capabilities are illustrated with an executable operational semantics of the Plan Execution Interchange Language (PLEXIL), a synchronous language developed by NASA to support autonomous spacecraft operations.
Extent
18 páginas.
Rights

© 2013 Elsevier B.V. Published by Elsevier B.V. All rights reserved.

URI: https://repositorio.escuelaing.edu.co/handle/001/1864
Collections

Collections

AD - CTG – Informática
References

1] M. AlTurki, J. Meseguer, Reduction semantics and formal analysis of Orc programs, in: Proceedings of the 3rd International Workshop on Automated Specification and Verification of Web Systems, WWV 2007, Electron. Notes Theor. Comput. Sci. 200 (3) (2008) 25–41

R. Bruni, J. Meseguer, Semantic foundations for generalized rewrite theories, Theor. Comput. Sci. 360 (1–3) (2006) 386–414.

C. Chira, T.F. Serbanuta, G. Stefanescu, P systems with control nuclei: The concept, J. Log. Algebr. Program. 79 (6) (2010) 326–333, Membrane computing and programming

M. Clavel, F. Durán, S. Eker, P. Lincoln, N. Martí-Oliet, J. Meseguer, C.L. Talcott (Eds.), All About Maude – A High-Performance Logical Framework, How to Specify, Program and Verify Systems in Rewriting Logic, Lect. Notes Comput. Sci., vol. 4350, Springer, 2007.

M. Clavel, J. Meseguer, M. Palomino, Reflection in membership equational logic, many-sorted equational logic, Horn logic with equality, and rewriting logic, Theor. Comput. Sci. 373 (1–2) (2007) 70–91.

G. Dowek, C. Muñoz, C. Pas˘ areanu, A small-step semantics of PLEXIL, Technical Report 2008-11, National Institute of Aerospace, Hampton, VA, 2008.

G. Dowek, C. Muñoz, C. Rocha, Rewriting logic semantics of a plan execution language, Electron. Proc. Theor. Comput. Sci. 18 (2010) 77–91.

T. Estlin, A. Jónsson, C. Pas˘ areanu, R. Simmons, K. Tso, V. Verna, Plan Execution Interchange Language (PLEXIL), Technical Memorandum ˘ TM-2006-213483, NASA, 2006.

[9] D. Lucanu, Strategy-based rewrite semantics for membrane systems preserves maximal concurrency of evolution rule actions, in: Proceedings of the 8th International Workshop on Reduction Strategies in Rewriting and Programming, WRS 2008, Electron. Notes Theor. Comput. Sci. 237 (2009) 107–125.

N. Martí-Oliet, J. Meseguer, A. Verdejo, A rewriting semantics for Maude strategies, Electron. Notes Theor. Comput. Sci. 238 (3) (2009) 227–247.

[11] J. Meseguer, Membership algebra as a logical framework for equational specification, in: F. Parisi-Presicce (Ed.), WADT, in: Lect. Notes Comput. Sci., vol. 1376, Springer, 1997, pp. 18–61.

J. Meseguer, P. Ölveczky, Formalization and correctness of the PALS architectural pattern for distributed real-time systems, in: J. Dong, H. Zhu (Eds.), Formal Methods and Software Engineering, in: Lect. Notes Comput. Sci., vol. 6447, Springer, Berlin / Heidelberg, 2010, pp. 303–320.

C. Rocha, Symbolic reachability analysis for rewrite theories, PhD thesis, University of Illinois at Urbana-Champaign, December 2012, https://www. ideals.illinois.edu/handle/2142/42200.

C. Rocha, H. Cadavid, C. Muñoz, R. Siminiceanu, A formal interactive verification environment for the plan execution interchange language, in: D. Latella, H. Treharne (Eds.), Proceedings of 9th International Conference on Integrated Formal Methods, iFM 2012, Pisa, Italy, in: Lect. Notes Comput. Sci., vol. 7321, June 2012, pp. 343–357.

C. Rocha, J. Meseguer, Proving safety properties of rewrite theories, in: A. Corradini, B. Klin, C. Cîrstea (Eds.), CALCO, in: Lect. Notes Comput. Sci., vol. 6859, Springer, 2011, pp. 314–328.

C. Rocha, C. Muñoz, G. Dowek, A formal library of set relations and its application to synchronous languages, Theor. Comput. Sci. 412 (37) (2011) 4853–4866.

T. Serbanuta, A rewriting approach to concurrent programming language design and semantics, PhD thesis, University of Illinois at Urbana-Champaign, December 2010, https://www.ideals.illinois.edu/handle/2142/18252.

T. Serbanuta, G. Stefanescu, G. Rosu, Defining and executing P systems with structured data in K, in: D. Corne, P. Frisco, G. Paun, G. Rozenberg, A. Salomaa (Eds.), Membrane Computing, in: Lect. Notes Comput. Sci., vol. 5391, Springer, Berlin/Heidelberg, 2009, pp. 374–393

Universities Space Research Association, The Plan Execution Interchange Language, http://plexil.sourceforge.net, June 2006.

P. Viry, Equational rules for rewriting logic, Theor. Comput. Sci. 285 (2) (2002) 487–517