Standard

Fast parsing for boolean grammars : A generalization of valiant's algorithm. / Okhotin, Alexander.

Developments in Language Theory - 14th International Conference, DLT 2010, Proceedings. 2010. p. 340-351 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6224 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Harvard

Okhotin, A 2010, Fast parsing for boolean grammars: A generalization of valiant's algorithm. in Developments in Language Theory - 14th International Conference, DLT 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6224 LNCS, pp. 340-351, 14th International Conference on Developments in Language Theory, DLT 2010, London, ON, Canada, 17/08/10. https://doi.org/10.1007/978-3-642-14455-4_31

APA

Okhotin, A. (2010). Fast parsing for boolean grammars: A generalization of valiant's algorithm. In Developments in Language Theory - 14th International Conference, DLT 2010, Proceedings (pp. 340-351). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6224 LNCS). https://doi.org/10.1007/978-3-642-14455-4_31

Vancouver

Okhotin A. Fast parsing for boolean grammars: A generalization of valiant's algorithm. In Developments in Language Theory - 14th International Conference, DLT 2010, Proceedings. 2010. p. 340-351. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-14455-4_31

Author

Okhotin, Alexander. / Fast parsing for boolean grammars : A generalization of valiant's algorithm. Developments in Language Theory - 14th International Conference, DLT 2010, Proceedings. 2010. pp. 340-351 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{1a4f88e07a09467a98def67e2c56a7f0,
title = "Fast parsing for boolean grammars: A generalization of valiant's algorithm",
abstract = "The well-known parsing algorithm for the context-free grammars due to Valiant ({"}General context-free recognition in less than cubic time{"}, Journal of Computer and System Sciences, 10:2 (1975), 308-314) is refactored and generalized to handle the more general Boolean grammars. The algorithm reduces construction of the parsing table to computing multiple products of Boolean matrices of various size. Its time complexity on an input string of length n is , where is the number of operations needed to multiply two Boolean matrices of size n ×n, which is O(n 2.376) as per the current knowledge.",
author = "Alexander Okhotin",
year = "2010",
month = nov,
day = "4",
doi = "10.1007/978-3-642-14455-4_31",
language = "English",
isbn = "3642144543",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "340--351",
booktitle = "Developments in Language Theory - 14th International Conference, DLT 2010, Proceedings",
note = "14th International Conference on Developments in Language Theory, DLT 2010 ; Conference date: 17-08-2010 Through 20-08-2010",

}

RIS

TY - GEN

T1 - Fast parsing for boolean grammars

T2 - 14th International Conference on Developments in Language Theory, DLT 2010

AU - Okhotin, Alexander

PY - 2010/11/4

Y1 - 2010/11/4

N2 - The well-known parsing algorithm for the context-free grammars due to Valiant ("General context-free recognition in less than cubic time", Journal of Computer and System Sciences, 10:2 (1975), 308-314) is refactored and generalized to handle the more general Boolean grammars. The algorithm reduces construction of the parsing table to computing multiple products of Boolean matrices of various size. Its time complexity on an input string of length n is , where is the number of operations needed to multiply two Boolean matrices of size n ×n, which is O(n 2.376) as per the current knowledge.

AB - The well-known parsing algorithm for the context-free grammars due to Valiant ("General context-free recognition in less than cubic time", Journal of Computer and System Sciences, 10:2 (1975), 308-314) is refactored and generalized to handle the more general Boolean grammars. The algorithm reduces construction of the parsing table to computing multiple products of Boolean matrices of various size. Its time complexity on an input string of length n is , where is the number of operations needed to multiply two Boolean matrices of size n ×n, which is O(n 2.376) as per the current knowledge.

UR - http://www.scopus.com/inward/record.url?scp=78049269471&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14455-4_31

DO - 10.1007/978-3-642-14455-4_31

M3 - Conference contribution

AN - SCOPUS:78049269471

SN - 3642144543

SN - 9783642144547

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 340

EP - 351

BT - Developments in Language Theory - 14th International Conference, DLT 2010, Proceedings

Y2 - 17 August 2010 through 20 August 2010

ER -

ID: 41142259