2014/02/13 by Namit Chaturvedi, Chaturvedi, Namit, Marcus Gelderie +1
Computer Science · #20M35 #68Q45 #68Q85 #F.1.1 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #acm:20M35 #acm:68Q45 #acm:68Q85 #cs.FL #msc:20M35 #msc:68Q45 #msc:68Q85
paper · pdf · doi:10.48550/arxiv.1402.3199
12 pages in main body, 4 pages in appendix, 2 figures
arxiv created 2014/02/13 · arxiv updated 2014/02/14
Mazurkiewicz traces describe concurrent behaviors of distributed systems. Trace-closed word languages, which are "linearizations" of trace languages, constitute a weaker notion of concurrency but still give us tools to investigate the latter. In this vein, our contribution is twofold. Firstly, we develop definitions that allow classification of ω-regular trace languages in terms of the corresponding trace-closed ω-regular word languages, capturing E-recognizable (reachability) and (deterministically) Büchi recognizable languages. Secondly, we demonstrate the first automata-theoretic result that shows the equivalence of ω-regular trace-closed word languages and Boolean combinations of deterministically I-diamond Büchi recognizable trace-closed languages.