On symmetry in strings, sequences and languages

Abstract

Starting from the concept of symmetry in algebra and mathematical analysis, we consider the property of a string to remain "unchanged" (member of a given language) by systematicaly interchanging the occurrences of two given symbols. Extensions to sets of symbols, then the symmetric closure and the symmetric kernel of a language are defined and studied, as well as the symmetry of bi-infinite sequences

Keywords:

• Symmetry
• symmetric closure
• Chomsky hierarchy
• decision problems
• bi-infinite sequences

¹ Research supported by the Academy of Finland,grant 11281

¹ Research supported by the Academy of Finland,grant 11281

Notes

¹ Research supported by the Academy of Finland,grant 11281