An algorithm for recognition of n-collapsing words

详细信息    查看全文

• 作者：I.V. Petrov
• 关键词：Deterministic finite automaton ; ; none ; color ; black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V1G-4PYP776-8&_mathId=mml12&_user=10&_cdi=5674&_rdoc=12&_acct=C000050221&_version=1&_userid=10&md5=b14f1c76
• 刊名：Theoretical Computer Science
• 出版年：2008
• 出版时间：4 February 2008
• 年：2008
• 卷：391
• 期：1-2
• 页码：99-108
• 全文大小：430 K

文摘

A word V1G-4PYP776-8&_mathId=mml1&_user=10&_cdi=5674&_rdoc=12&_acct=C000050221&_version=1&_userid=10&md5=41fede2b5c66247eb5a0d9ab845a3a7c"" title=""Click to view the MathML source"">w over a finite alphabet Σ is n-collapsing if for an arbitrary deterministic finite automaton , the inequality |δ(Q,w)|≤|Q|−n holds provided that |δ(Q,u)|≤|Q|−n for some word uΣ⁺ (depending on ). We prove that the property of n-collapsing is algorithmically recognizable for any given positive integer n. We also prove that the language of all n-collapsing words is context-sensitive.