PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Enumeration of words in context-free languages using Haskell

Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
PL
Haskellowa implementacja wyliczania słów języków bezkontekstowych
Języki publikacji
EN
Abstrakty
EN
The cross-section enumeration problem is to list all words of length n in a language L in lexicographic order. We present the Haskell implementation of an algorithm for the cross-section enumeration problem for any language defined by a context-free grammar without unit productions and without λ-productions.
PL
Jednym z rozważanych problemów kombinatorycznych jest wyliczenie w porządku leksykograficznym wszystkich słów o długości n należących do pewnego języka L. W niniejszym artykule zaprezentowano algorytm – wraz ze stosownym kodem w języku Haskell – służący do takiego wyliczania. Zakładamy, że język L zdefiniowany jest za pomocą gramatyki bezkontekstowej bez produkcji jednostkowych i bez λ-produkcji.
Czasopismo
Rocznik
Strony
5--17
Opis fizyczny
Bibliogr. 13 poz.
Twórcy
autor
  • Silesian University, Institute of Computer Science, ul. Będzińska 39, 41-200 Sosnowiec, Poland
Bibliografia
  • 1. Ackerman M., Shallit J.: Efficient enumeration of words in regular languages. Theoretical Computer Science, vol. 410, 2009, p. 3461÷3470.
  • 2. Adams S.: Efficient sets: a balancing act. Journal of Functional Programming, vol. 3, 11993, p. 553÷562.
  • 3. Andrews G.E.: The Theory of Partitions. Encyclopaedia of Mathematics and Its Applications 2, Addison-Wesley (1976), reissued CUP 1998.
  • 4. Asveld P.: Generating all permutations by context-free grammars in Chomsky normal form. Theoretical Computer Science, vol. 125, 2006, p. 315÷328.
  • 5. Bertoni A., Goldwurm M., Santini M.: Random generation for finitely ambiguous context-free languages. Theoretical Informatics and Applications, vol. 35, 2001, p. 499÷512.
  • 6. Goldwurm M.: Random generation of words in an algebraic language in linear binary space. Information Processing Letters, vol. 54, 1995, p. 229÷233.
  • 7. Haskell libraries. URL http://www.haskell.org/ghc/docs/latest/html/libraries
  • 8. Hopcroft J.E., Ullman J.D.: Introduction to automata theory, languages and computation. Addison-Wesley, 1979.
  • 9. Hutton G.: Programming in Haskell. Cambridge University Press, 2007.
  • 10. Mäkinen E.: On lexicographic enumeration of regular and context-free languages. Acta Cybernetica, vol. 13, 1997, p. 55÷61.
  • 11. Mandoiu I.I., Zelikovsky A.Z. (Eds.): Bioinformatics Algorithms: Techniques and Applications. John Wiley & Sons, 2008.
  • 12. Papadimitriou C.H., Steiglitz K.: Combinatorial Optimization: Algorithms and Complexity. Dover Publications, 1998.
  • 13. Rabhi F., Lapalme G.: Algorithms: A Functional Programming Approach. AddisonWesley, 1999.
Uwagi
Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017)
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-14ea4679-5163-40db-9b33-280c023ab00a
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.