Derivatives of Existentially Regular Trace Languages: Tarmo Uustalu

ICE-TCS seminar

  • 11.12.2018, 12:15 - 13:00


ICE-TCS seminar #324

Date and time: Tuesday, 11 December 2018, 12:10-13:00
Location: Room M1.10 (note the non-standard room)
Speaker: Tarmo Uustalu (Reykjavik University) 

Title: Derivatives of Existentially Regular Trace Languages

Abstract: We provide syntactic (expression-level) language derivative operations, both in the styles of Brzozowski and Antimirov, for trace closures of regular word languages wrt. an independence relation on the alphabet. The Brzozowski and Antimirov style derivatives essentially define functional resp. relational small-step operational semantics of an (abstracted) sequential programming language where some instructions,
given by the independence relation, can be reordered without any observable consequences. Our development is motivated by the fact that some aspects of relaxed memories can be explained by allowing the threads of a concurrent program to be reordered in this manner. 

This is joint work with Hendrik Maarand (Tallinn University of Technology).