Name
Abstract | ||
|---|---|---|
Multi-threaded programs with recursion are naturally modeled as multi-pushdown systems. The behaviors are represented as multiply nested words (MNWs), which are words enriched with additional binary relations for each stack matching a push operation with the corresponding pop operation. Any MNW can be decomposed by two basic and natural operations: shuffle of two sequences of factors and merge of consecutive factors of a sequence. We say that the split-width of a MNW is k if it admits a decomposition where the number of factors in each sequence is at most k. The MSO theory of MNWs with split-width k is decidable. We introduce two very general classes of MNWs that strictly generalize known decidable classes and prove their MSO decidability via their split-width and obtain comparable or better bounds of tree-width of known classes. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-32940-1_38 | CONCUR |
Keywords | Field | DocType |
multi-threaded program,natural operation,multi-pushdown system,corresponding pop operation,split-width k,mso decidability,push operation,known class,decidable class,additional binary relation,mso theory | Discrete mathematics,Binomial options pricing model,Combinatorics,Nested word,Binary relation,Decidability,Tree automaton,Merge (version control),Mathematics,Recursion | Conference |
Volume | ISSN | Citations |
7454 | 0302-9743 | 18 |
PageRank | References | Authors |
0.71 | 23 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aiswarya Cyriac | 1 | 58 | 3.31 |
| Paul Gastin | 2 | 1165 | 75.66 |
| K. Narayan Kumar | 3 | 139 | 6.98 |