String Rewriting Systems

Michał Trybulec

Displaying similar documents to “String Rewriting Systems”

Undecidability of infinite post correspondence problem for instances of Size 9

Vesa Halava, Tero Harju (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

In the infinite Post Correspondence Problem an instance consists of two morphisms and , and the problem is to determine whether or not there exists an infinite word such that . This problem was shown to be undecidable by Ruohonen (1985) in general. Recently Blondel and Canterini ( (2003) 231–245) showed that this problem is undecidable for domain alphabets of size 105. Here we give a proof that the infinite Post Correspondence Problem is undecidable for instances...

Semi-commutations and partial commutations

M. Clerbout, Y. Roos, I. Ryl (2000)

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

Similarity:

A Hierarchy of Automatic -Words having a Decidable MSO Theory

Vince Bárány (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

We investigate automatic presentations of -words. Starting points of our study are the works of Rigo and Maes, Caucal, and Carton and Thomas concerning lexicographic presentation, MSO-interpretability in algebraic trees, and the decidability of the MSO theory of morphic words. Refining their techniques we observe that the lexicographic presentation of a (morphic) word is in a certain sense canonical. We then generalize our techniques to a hierarchy of classes of -words enjoying...

Some Algebraic Properties of Machine Poset of Infinite Words

Aleksandrs Belovs (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

The complexity of infinite words is considered from the point of view of a transformation with a Mealy machine that is the simplest model of a finite automaton transducer. We are mostly interested in algebraic properties of the underlying partially ordered set. Results considered with the existence of supremum, infimum, antichains, chains and density aspects are investigated.

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:...

On a class of Thue-Morse type sequences.

Astudillo, Ricardo (2003)

Journal of Integer Sequences [electronic only]

Similarity:

On ${(R_{0})}_{s}$ -spaces

Maheshwari, S.N., Prasad, R. (1975)

Portugaliae mathematica

Similarity:

Corrections to “Some generalizations of $T_{D}$ -spaces” and “A generalization of normal spaces”.

Nayar, Bhamini M.P. (1997)

Matematichki Vesnik

Similarity:

Sturmian jungle (or garden?) on multiliteral alphabets

L&amp;#039;ubomíra Balková, Edita Pelantová, Štěpán Starosta (2010)

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

Similarity:

The properties characterizing sturmian words are considered for words on multiliteral alphabets. We summarize various generalizations of sturmian words to multiliteral alphabets and enlarge the list of known relationships among these generalizations. We provide a new equivalent definition of rich words and make use of it in the study of generalizations of sturmian words based on palindromes. We also collect many examples of infinite words to illustrate differences in the generalized...