Displaying similar documents to “On the density of languages representing finite set partitions.”

Hierarchies and reducibilities on regular languages related to modulo counting

Victor L. Selivanov (2009)

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

Similarity:

We discuss some known and introduce some new hierarchies and reducibilities on regular languages, with the emphasis on the quantifier-alternation and difference hierarchies of the quasi-aperiodic languages. The non-collapse of these hierarchies and decidability of some levels are established. Complete sets in the levels of the hierarchies under the polylogtime and some quantifier-free reducibilities are found. Some facts about the corresponding degree structures are established. As an...

Extending regular expressions with homomorphic replacement

Henning Bordihn, Jürgen Dassow, Markus Holzer (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We define H- and EH-expressions as extensions of regular expressions by adding homomorphic and iterated homomorphic replacement as new operations, resp. The definition is analogous to the extension given by Gruska in order to characterize context-free languages. We compare the families of languages obtained by these extensions with the families of regular, linear context-free, context-free, and EDT0L languages. Moreover, relations to language families based on patterns, multi-patterns,...

Bidirectional string assembling systems

Martin Kutrib, Matthias Wendlandt (2014)

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

Similarity:

We introduce and investigate several variants of a bidirectional string assembling system, which is a computational model that generates strings from copies of assembly units. The underlying mechanism is based on two-sided piecewise assembly of a double-stranded sequence of symbols, where the upper and lower strand have to match. The generative capacities and the relative power of the variants are our main interest. In particular, we prove that bidirectional string assembling system...

Formal Languages - Concatenation and Closure

Michał Trybulec (2007)

Formalized Mathematics

Similarity:

Formal languages are introduced as subsets of the set of all 0-based finite sequences over a given set (the alphabet). Concatenation, the n-th power and closure are defined and their properties are shown. Finally, it is shown that the closure of the alphabet (understood here as the language of words of length 1) equals to the set of all words over that alphabet, and that the alphabet is the minimal set with this property. Notation and terminology were taken from [5] and [13]. MML identifier:...

A morphic approach to combinatorial games : the Tribonacci case

Eric Duchêne, Michel Rigo (2008)

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

Similarity:

We propose a variation of Wythoff’s game on three piles of tokens, in the sense that the losing positions can be derived from the Tribonacci word instead of the Fibonacci word for the two piles game. Thanks to the corresponding exotic numeration system built on the Tribonacci sequence, deciding whether a game position is losing or not can be computed in polynomial time.

Consensual languages and matching finite-state computations

Stefano Crespi Reghizzi, Pierluigi San Pietro (2011)

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

Similarity:

An ever present, common sense idea in language modelling research is that, for a word to be a valid phrase, it should comply with multiple constraints at once. A new language definition model is studied, based on agreement or consensus between similar strings. Considering a regular set of strings over a bipartite alphabet made by pairs of unmarked/marked symbols, a match relation is introduced, in order to specify when such strings agree. Then a regular set over the bipartite alphabet...

On the expressive power of the shuffle operator matched with intersection by regular sets

Joanna Jȩdrzejowicz, Andrzej Szepietowski (2001)

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

Similarity:

We investigate the complexity of languages described by some expressions containing shuffle operator and intersection. We show that deciding whether the shuffle of two words has a nonempty intersection with a regular set (or fulfills some regular pattern) is NL-complete. Furthermore we show that the class of languages of the form L ∩ R , with a shuffle language L and a regular language R , contains non-semilinear languages and does not form a family of mildly context- sensitive languages. ...