TR06-01 (2006) – Strategies and Tactics in Operational Semantics

Oana Andrei, Gabriel Ciobanu, Dorel Lucanu

We refer to strategies setting the objective of a computation step rather than to evaluationstrategies (as eager or lazy evaluations). We use these strategies to define semantics of a systemstarting from its elementary operational entities, and then combining them. The tactics of astrategy are given by rewriting steps. While a strategy is at a higher level and defines “what isthe goal” of a computation, the tactics are at a lower level and tell “how it is possible to reachthe goal”.

We use rewriting systems as a general model of computing. In this framework we give anoperational semantics of the strategic transitions in terms of tactical rewritings. The approachis inspired by a new model of computation given by membrane systems. We define the strategysemantics for membrane systems involving the maximal parallel rewriting and priorities. Weshow that strategies are not powerful enough to define alone the semantics of membrane systemsinvolving promoters. This is possible when we encode the state of the membrane in a richerstructure.

Bibtex

@TechReport{stos,
author = "Oana Andrei and Gabriel Ciobanu and Dorel Lucanu ",
title = " Strategies and Tactics in Operational Semantics",
institution = "``Al.I.Cuza'' University of Ia{c s}i, 
                 Faculty of Computer Science",
year = "2006",
number = "TR 06-01",
note = "URL:http://www.infoiasi.ro/~tr/tr.pl.cgi"
}