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

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

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

我建议研究结合理论计算机科学、组合学、代数和数论方面的问题，沿着我最近与Jean-Paul Allouche合著的专著“自动序列：理论、应用、概括”的主题，剑桥大学出版社于2003年出版。特别是，我计划研究涉及描述复杂性、单词组合、形式语言和有限自动机等主题的问题。