Discovering grammar of an unknown text as an optimisation problem

• Autorzy: Ryszawa P. A.

Warianty tytułu

PL

Odkrywanie gramatyki dla nieznanego tekstu jako zadanie optymalizacyjne

• Języki publikacji: EN

Abstrakty

EN

This paper concerns the problem of discovering an unknown grammar from a text sample. The discovering methods are formulated as optimisation problems based on a binary representation of context-sensitive grammars. The representation starts with a longest possible vector of bits to, finally, make it more compact so as to be usable in practical applications. For the sake of simplicity, considered are only noncontracting (length-preserving) grammars of order 2, excluding productions of the form P: A→ B and those deriving the empty string, i.e P: A → ε.

PL

Niniejszy artykuł dotyczy problemu odkrywania nieznanej gramatyki z próbki tekstu. Metody odkrywania zostały sformułowane jako zadania optymalizacyjne oparte na binarnej reprezentacji gramatyk kontekstowych. Reprezentacja ta, początkowo jako najdłuższy możliwy wektor bitów, ostatecznie została skrócona do zwięzłej postaci, nadającej się do wykorzystania praktycznego. Dla uproszczenia uwzględniono tylko gramatyki nieskracające rzędu 2, z wyłączeniem produkcji postaci P: A→ B i tych wyprowadzających łańcuch pusty, tj. P: A → ε.

Słowa kluczowe

EN

context-sensitive language; formal grammar; noncontracting grammar; binary representation; optimisation problem

PL

język kontekstowy; gramatyka formalna; gramatyka nieskracająca; reprezentacja binarna; zadanie optymalizacyjne

• Wydawca: Institute of Computer and Information Systems, Faculty of Cybernetics, Military University of Technology
• Czasopismo: Computer Science and Mathematical Modelling
• Rocznik: 2017
• Tom: No. 6
• Strony: 15--22
• Opis fizyczny: Bibliogr. 11 poz., tab.

Twórcy

autor

Ryszawa P. A.

• Military University of Technology, Faculty of Cybernetics, Urbanowicza Str. 2, 00-908 Warsaw, Poland

Bibliografia

• [1] Boyd S., Vandenberghe L., Convex Optimization, 7th Edition, Cambridge University Press, 2009.
• [2] Chudy M., Wybrane algorytmy optymalizacji, EXIT, 2014.
• [3] Foryś M., Foryś W., Teoria automatów i języków formalnych, EXIT, 2005.
• [4] Galas Z., Nykowski I., Żółkiewski Z., Programowanie wielokryterialne, PWE, 1987.
• [5] Hopcroft J.E., Motwani R., Ullman J.D., Introduction to Automata Theory, Languages and Computation, 2nd Edition, Pearson Education, 2001.
• [6] Kusiak J., Danielewska-Tułecka A., Oprocha P., Optymalizacja, PWN SA, 2009.
• [7] Linz P., An Introduction to Formal Languages and Automata, 5th Edition, Jones & Bartlett Learning, 2012.
• [8] Martin J.C., Introduction to Languages and the Theory of Computation, 4th Edition, McGraw-Hill, 2011.
• [9] Taha H. A., Operations research: An Introduction, 8th Edition, Pearson Education, 2008.
• [10] Woods W.A., “Context-Sensitive Parsing”, Communications of the ACM, Vol. 13, No. 7, 437–445 (1970).
• [11] Younger D.H., “Recognition and Parsing of Context-Free Grammars in Time n³”, Information and Control, Vol. 10, Issue 2, 189–208 (1967).