On the Computational Complexity of Synchronized Context-Free Languages
| dc.creator | Bordihn,Henning | |
| dc.creator | Holzer,Markus | |
| dc.date | 2002 | |
| dc.date.accessioned | 2024-02-06T12:51:38Z | |
| dc.date.available | 2024-02-06T12:51:38Z | |
| dc.description | We introduce counter synchronized contextfree grammars and investigate their generative power. It turns out that the family of counter synchronized contextfree languages is a proper superset of the family of contextfree languages and is strictly contained in the family of synchronized contextfree languages. Moreover, we establish the space and time complexity of the fixed membership, the general membership, and the nonemptiness problem for synchronized and counter synchronized contextfree 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 PSpacecompleteness of the general membership problem of synchronized contextfree grammars relies on a remarkable normal form for these grammars, namely for every synchronized contextfree grammar one can effectively construct and equivalent grammar of same type without nonsynchronizing nonterminals, except the axiom. 1.) C. S. Calude, K. Salomaa, S. Yu (eds.). Advances and Trends in Automata and Formal Languages. A Collection of Papers in Honour of the 60th Birthday of Helmut Jürgensen. | |
| dc.format | text/html | |
| dc.identifier | https://doi.org/10.3217/jucs-008-02-0119 | |
| dc.identifier | https://lib.jucs.org/article/27848/ | |
| dc.identifier.uri | https://openrepository.mephi.ru/handle/123456789/8100 | |
| dc.language | en | |
| dc.publisher | Journal of Universal Computer Science | |
| dc.relation | info:eu-repo/semantics/altIdentifier/eissn/0948-6968 | |
| dc.relation | info:eu-repo/semantics/altIdentifier/pissn/0948-695X | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | J.UCS License | |
| dc.source | JUCS - Journal of Universal Computer Science 8(2): 119-140 | |
| dc.subject | formal languages | |
| dc.subject | synchronized grammars | |
| dc.subject | decision problems | |
| dc.subject | computational complexity | |
| dc.title | On the Computational Complexity of Synchronized Context-Free Languages | |
| dc.type | Research Article |