Record Details

Asynchronous automata-theoretic characterization of aperiodic trace languages

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Asynchronous automata-theoretic characterization of aperiodic trace languages
 
Creator ADSUL, B
SOHONI, M
 
Subject monoids
 
Description We characterize aperiodic distributed behaviours, modelled as Mazurkiewicz traces in terms of a very natural cascade product of the gossip automaton with a counter-free asynchronous automaton. The characterization strengthens the fundamental results of Schutzenberger and, McNaughton and Papert and implies that star-free, equivalently, first-order-definable trace languages admit counter-free asynchronous acceptors modulo the gossip automaton.
 
Publisher SPRINGER-VERLAG BERLIN
 
Date 2011-10-23T17:20:03Z
2011-12-15T09:11:15Z
2011-10-23T17:20:03Z
2011-12-15T09:11:15Z
2004
 
Type Article; Proceedings Paper
 
Identifier FSTTCS 2004: FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE,3328,84-96
3-540-24058-6
0302-9743
http://dspace.library.iitb.ac.in/xmlui/handle/10054/15186
http://hdl.handle.net/100/1950
 
Source 24th International Conference on Foundations of Software Technology and Theoretical Computer Science,Chennai, INDIA,DEC 16-18, 2004
 
Language English