Descriptional complexity, combinatorics on words, formal languages and number theory

描述复杂性、单词组合学、形式语言和数论

• 批准号: 105829-2008
• 负责人: Shallit, Jeffrey
• 金额: $ 2.99万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2008
• 资助国家: 加拿大
• 起止时间: 2008-01-01 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=390988
• 关键词: Descriptional; complexity; combinatorics; words; formal

I propose to investigate problems combining aspects of theoretical computer science, combinatorics, algebra, and number theory, along the lines of the topics in my recent monograph with Jean-Paul Allouche, "Automatic Sequences: Theory, Applications, Generalizations", published by Cambridge University Press in 2003. In particular, I plan to work on problems involving the topics of descriptional complexity, conbinatorics on words, formal languages, and finite automata.

我建议调查的问题相结合的方面，理论计算机科学，组合，代数和数论，沿着线的主题，在我最近的专着与让-保罗Allouche，“自动序列：理论，应用，推广”，出版的剑桥大学出版社于2003年。 特别是，我计划工作的问题，涉及的主题的概念复杂性，conbinatorics的话，形式语言和有限自动机。