Computer Science – Formal Languages and Automata Theory
Scientific paper
2011-08-18
EPTCS 63, 2011, pp. 13-19
Computer Science
Formal Languages and Automata Theory
In Proceedings WORDS 2011, arXiv:1108.3412
Scientific paper
10.4204/EPTCS.63.2
I am going to compare well-known properties of infinite words with those of infinite permutations, a new object studied since middle 2000s. Basically, it was Sergey Avgustinovich who invented this notion, although in an early study by Davis et al. permutations appear in a very similar framework as early as in 1977. I am going to tell about periodicity of permutations, their complexity according to several definitions and their automatic properties, that is, about usual parameters of words, now extended to permutations and behaving sometimes similarly to those for words, sometimes not. Another series of results concerns permutations generated by infinite words and their properties. Although this direction of research is young, many people, including two other speakers of this meeting, have participated in it, and I believe that several more topics for further study are really promising.
No associations
LandOfFree
Infinite permutations vs. infinite words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Infinite permutations vs. infinite words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Infinite permutations vs. infinite words will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-180555