Priorities in Operational Semantics and Term Rewriting


EPSRC Overseas Travel Grant EP/D001307/1, GPB 7,270


April 2005 - March 2008


Operational semantics and term rewriting are well established fields of theoretical computer science. Priority, according to Oxford Paperback Dictionary, means "being earlier or more important" and indicates that an object has "precedence in rank" when compared with other objects. In the context of this project, priorities specify the order of application of operational rules and rewrite rules when deriving transitions and rewrites of terms. The initial research on priorities in operational semantics and term rewriting shows that they extend expressiveness. Priorities replace awkward negative premises in SOS rules and they help to control the ambiguity of term rewriting and to improve the modularity and confluence. The aim of this project is to establish new (and strengthen the existing) collaboration links with the scientists in the Netherlands and Japan in order to explore further the potential of priorities in operational semantics and term rewriting. We intend to extend the Ordered SOS framework with additional features such as predicates and complex terms in the premises, prove congruence results, investigate fully expressive formats and explore their applications in concurrency. In term rewriting with priorities, we plan to re-investigate its operational semantics, find methods for internalising rewrite strategies with priority orders, and explore reasoning for systems with infinite behaviour. Finally, we aim to study Term Deduction Systems with priorities as uniform formalisms for representing such diverse notions as Ordered SOS, priority term rewriting and logic programming languages such as Prolog.


I Ulidowski

Share this page:

Contact Us

Admissions Enquiries:
BSc: +44 (0) 116 252 5280
MSc: +44 (0) 116 252 2265
E: BSc
E: MSc

Departmental Enquiries:
T: +44 (0) 116 252 2129/3887
F: +44 (0) 116 252 3604

Dept of Informatics
University of Leicester
Leicester, LE1 7RH
United Kingdom


DisabledGo logo

The University of Leicester is committed to equal access to our facilities. DisabledGo has a detailed accessibility guide for the Informatics Building.