Pattern avoidability with involution

DOI10.4204/EPTCS.63.10MaRDI QIDQ2789515zbMATH OpenOpenAlexFDO

Authors Bastian Bischoff, Dirk Nowotka

Publication date 1 March 2016

Published in Electronic Proceedings in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.3622, http://www.emis.de/proceedings/Words2011/paper-8.html?WORDS2011.10

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: An infinte word w avoids a pattern p with the involution t if there is no substitution for the variables in p and no involution t such that the resulting word is a factor of w. We investigate the avoidance of patterns with respect to the size of the alphabet. For example, it is shown that the pattern a t(a) a can be avoided over three letters but not two letters, whereas it is well known that a a a is avoidable over two letters.

Recommendations

• Unary patterns with involution
• scientific article; zbMATH DE number 4035171
• Avoidable patterns on two letters
• Avoidability of palindrome patterns
• THE EXISTENCE OF A PATTERN WHICH IS 5-AVOIDABLE BUT 4-UNAVOIDABLE

Cited in

(12)

• Avoidability of circular formulas
• Cubic patterns with permutations
• On the aperiodic avoidability of binary patterns with variables and reversals
• Avoidability index for binary patterns with reversal
• New problems of pattern avoidance
• Unary patterns with involution
• Decision algorithms for Fibonacci-automatic words. II: Related sequences and avoidability
• Pattern Avoidance in Reverse Double Lists
• THE EXISTENCE OF A PATTERN WHICH IS 5-AVOIDABLE BUT 4-UNAVOIDABLE
• Involutive Completion to Avoid LBB Condition
• The syntactic monoid of -free palindromic words
• Growth rate of binary words avoiding \(xxx^{R}\)

This page was built for publication: Pattern avoidability with involution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2789515)