Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: lexicographic order

Sortuj według:

Ogranicz wyniki do:

Enumeration of words in context-free languages using Haskell

Wieczorek W.

Studia Informatica

2017

Vol. 38, nr 1B

5--17

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.

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.

Simple Linear Comparison of Strings in V -order

Alatabbi A., Daykin J. W., Rahman M. S., Smyth W. F.

Fundamenta Informaticae

2015

Vol. 139, nr 2

115--126

In this paper we focus on a total (but non-lexicographic) ordering of strings called V - order. We devise a new linear-time algorithm for computing the V -comparison of two finite strings. In comparison with the previous algorithm in the literature, our algorithm is both conceptually simpler, based on recording letter positions in increasing order, and more straightforward to implement, requiring only linked lists.

Some Characterizations of Sturmian Words in Terms of the Lexicographic Order

Bucci M., De Luca A., Zamboni L. Q.

Fundamenta Informaticae

2012

Vol. 116, nr 1-4

25-33

In this paper we present three new characterizations of Sturmian words based on the lexicographic ordering of their factors.

Combinatorics of Unique Maximal Factorization Families (UMFFs)

Daykin D.E., Daykin J.W., Smyth W.F. (Bill)

Fundamenta Informaticae

2009

Vol. 97, nr 3

295-309

Suppose a set W of strings contains exactly one rotation (cyclic shift) of every primitive string on some alphabet Σ. Then W is a circ-UMFF if and only if every word in Σ+ has a unique maximal factorization over W. The classic circ-UMFF is the set of Lyndon words based on lexicographic ordering (1958). Duval (1983) designed a linear sequential Lyndon factorization algorithm; a corresponding PRAMparallel algorithmwas described by J. Daykin, Iliopoulos and Smyth (1994). Daykin and Daykin defined new circ-UMFFs based on various methods for totally ordering sets of strings (2003), and further described the structure of all circ-UMFFs (2008). Here we prove new combinatorial results for circ-UMFFs, and in particular for the case of Lyndon words. We introduce Acrobat and Flight Deck circ-UMFFs, and describe some of our results in terms of dictionaries. Applications of circ-UMFFs pertain to structured methods for concatenating and factoring strings over ordered alphabets, and those of Lyndon words are wide ranging and multidisciplinary.