Abstract | ||
---|---|---|
We describe a general decomposition mechanism to express the derivation relation of a word rewriting system R as the composition of a (regular) substitution followed by the derivation relation of a system R′ ∪ D, where R′ is a strict sub-system of R and D is the Dyck rewriting system. From this decomposition, we deduce that the system R (resp. R-1) preserves regular (resp. context-free) languages whenever R′ ∪ D (resp. its inverse) does. From this we can deduce regularity and context-freeness preservation properties for a generalization of tagged. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1007/978-3-642-19805-2_15 | FoSSaCS |
Keywords | Field | DocType |
context-freeness preservation property,general decomposition mechanism,strict sub-system,derivation relation,system r,context free language | Inverse,Discrete mathematics,Theoretical computer science,Confluence,Rewriting,Mathematics | Conference |
Volume | ISSN | Citations |
6604 | 0302-9743 | 1 |
PageRank | References | Authors |
0.37 | 12 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Didier Caucal | 1 | 470 | 39.15 |
Trong Hieu Dinh | 2 | 1 | 0.37 |