Name
Abstract | ||
|---|---|---|
We introduce counter synchronized context-free grammars and investigate their generative power. It turns out that the family of counter synchronized context-free languages is proper superset of the family of context-free languages and is strictly contained in the family of synchronized context-free languages. Moreover, we establish the space and time complexity of the fixed membership, the general membership, and the non-emptiness problem for synchronized and counter synchronized context-free languages and solve the mentioned complexity questions in terms of completeness results for complexity classes. In this way we present new complete problems for LOG(CF), NP and PSpace It is worth to mention that the main theorem on the PSpace completeness of the general membership problem of synchronized context-free grammars relies on remarkable normal form for these grammars, namely for every synchronized context-free grammar one can effectively construct and equivalent grammar of same type without non-synchronizing nonterminals, except the axiom. |
Year | Venue | Keywords |
|---|---|---|
2002 | JOURNAL OF UNIVERSAL COMPUTER SCIENCE | formal languages,synchronized grammars,decision problems,computational complexity,l |
DocType | Volume | Issue |
Journal | 8 | 2 |
Citations | PageRank | References |
3 | 0.52 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henning Bordihn | 1 | 167 | 31.96 |
| Markus Holzer | 2 | 138 | 12.30 |