Pattern selector grammars and several parsing algorithms in the context- free style (Q1081314)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Pattern selector grammars and several parsing algorithms in the context- free style |
scientific article |
Statements
Pattern selector grammars and several parsing algorithms in the context- free style (English)
0 references
1985
0 references
Pattern selector grammars are defined in general. We concentrate on the study of special grammars, the pattern selectors of which contain precisely k ''one''s \((0^*(10^*)^ k)\) or k adjacent ''one''s \((0^*1^ k0^*)\). This means that precisely k symbols (resp. k adjacent symbols) in each sentential form are rewritten. The main results concern parsing algorithms and the complexity of the membership problem. We first obtain a polynomial bound on the shortest derivation and hence an NP time bound for parsing. In the case \(k=2\), we generalize the well- known context-free dynamic programming type algorithms, which run in polynomial time. It is shown that the generated languages, for \(k=2\), are log-space reducible to the context-free languages. The membership problem is thus solvable in \(\log^ 2\) space.
0 references
complexity of the membership problem
0 references
polynomial bound on the shortest derivation
0 references
NP time bound for parsing
0 references
context-free languages
0 references