Record Details

Local normal forms for logics over traces

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Local normal forms for logics over traces
 
Creator ADSUL, B
SOHONI, M
 
Subject mazurkiewicz traces
 
Description We investigate local and global paradigms of reasoning about distributed behaviours, modelled as Mazurkiewicz traces, in the context of first-order and monadic second-order logics. We describe new normal forms for properties expressible in these logics. The first normal form, surprisingly, yields a decomposition of a global property as a boolean combination of local properties. The second normal form strengthens McNaughton's theorem and states that global properties of infinite behaviours may also be described as boolean combinations of recurring properties of finite local histories of the behaviours. We briefly touch upon some of the interesting applications of these normal forms.
 
Publisher SPRINGER-VERLAG BERLIN
 
Date 2011-10-23T14:09:15Z
2011-12-15T09:11:11Z
2011-10-23T14:09:15Z
2011-12-15T09:11:11Z
2002
 
Type Article; Proceedings Paper
 
Identifier FST TCS 2002: FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEOETICAL COMPUTER SCIENCE, PROCEEDINGS,2556,47-58
3-540-00225-1
0302-9743
http://dspace.library.iitb.ac.in/xmlui/handle/10054/15150
http://hdl.handle.net/100/1908
 
Source 22nd International Conference on Foundations of Software Technology and Theoretical Computer Science,KANPUR, INDIA,DEC 12-14, 2002
 
Language English