Improved normal form for grammars with one-sided contexts. / Okhotin, Alexander.
Descriptional Complexity of Formal Systems - 15th International Workshop, DCFS 2013, Proceedings. 2013. p. 205-216 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8031 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Improved normal form for grammars with one-sided contexts
AU - Okhotin, Alexander
N1 - Funding Information: Research supported by the Academy of Finland under grant 257857 .
PY - 2013
Y1 - 2013
N2 - Formal grammars equipped with operators for specifying the form of the context of a substring were recently studied by Barash and Okhotin ("Defining contexts in context-free grammars", LATA 2012), further extending the author's ("Conjunctive grammars", DCAGRS 2000) earlier work on propositional connectives in grammars. These grammars allow two types of context specifications: for a substring w of a string uwv, a left context operator ◁D states that u is of the form described by D, while the extended left context operator ⊴E states that uw is described by E. This paper establishes a normal form for these grammars, in which extended left contexts are never used, while left contexts may be applied only for individual symbols, so that all rules are of the form A → B1C1 &⋯& BnCn or A → a & ◁D. This eliminates circular dependencies in the grammar and allows simplifying the known parsing algorithm. Some further improvements to the algorithm accelerate it from time O(n3) to time O(n3/log n).
AB - Formal grammars equipped with operators for specifying the form of the context of a substring were recently studied by Barash and Okhotin ("Defining contexts in context-free grammars", LATA 2012), further extending the author's ("Conjunctive grammars", DCAGRS 2000) earlier work on propositional connectives in grammars. These grammars allow two types of context specifications: for a substring w of a string uwv, a left context operator ◁D states that u is of the form described by D, while the extended left context operator ⊴E states that uw is described by E. This paper establishes a normal form for these grammars, in which extended left contexts are never used, while left contexts may be applied only for individual symbols, so that all rules are of the form A → B1C1 &⋯& BnCn or A → a & ◁D. This eliminates circular dependencies in the grammar and allows simplifying the known parsing algorithm. Some further improvements to the algorithm accelerate it from time O(n3) to time O(n3/log n).
UR - http://www.scopus.com/inward/record.url?scp=84884469507&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-39310-5_20
DO - 10.1007/978-3-642-39310-5_20
M3 - Conference contribution
AN - SCOPUS:84884469507
SN - 9783642393099
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 205
EP - 216
BT - Descriptional Complexity of Formal Systems - 15th International Workshop, DCFS 2013, Proceedings
T2 - 15th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2013
Y2 - 22 July 2013 through 25 July 2013
ER -
ID: 78945181