Displaying similar documents to “Strings with maximally many distinct subsequences and substrings.”

Random generation for finitely ambiguous context-free languages

Alberto Bertoni, Massimiliano Goldwurm, Massimo Santini (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We prove that a word of length n from a finitely ambiguous context-free language can be generated at random under uniform distribution in O ( n 2 log n ) time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time 1 -NAuxPDA with polynomially bounded ambiguity.

Monoid presentations of groups by finite special string-rewriting systems

Duncan W. Parkes, V. Yu. Shavrukov, Richard M. Thomas (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We show that the class of groups which have monoid presentations by means of finite special [ λ ] -confluent string-rewriting systems strictly contains the class of plain groups (the groups which are free products of a finitely generated free group and finitely many finite groups), and that any group which has an infinite cyclic central subgroup can be presented by such a string-rewriting system if and only if it is the direct product of an infinite cyclic group and a finite cyclic group. ...

Transcendence of numbers with an expansion in a subclass of complexity 2 + 1

Tomi Kärki (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

We divide infinite sequences of subword complexity into four subclasses with respect to left and right special elements and examine the structure of the subclasses with the help of Rauzy graphs. Let ≥ 2 be an integer. If the expansion in base of a number is an Arnoux-Rauzy word, then it belongs to Subclass I and the number is known to be transcendental. We prove the transcendence of numbers with expansions in the subclasses II and III.