A lower-bound for the number of productions required for a certain class of languages期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

A lower-bound for the number of productions required for a certain class of languages

Authors:	Brian Alspach Peter Eades Gordon Rose

Affiliation:	Department of Mathematics, Simon Fraser University, Burnaby, B.C. V5A 1S6, Canada;Department of Computer Science, University of Queensland, St. Lucia, Queensland, Australia 4067

Abstract:	W. Bucher, K. Culik II, H. Maurer and D. Wotschke (Theoretical Computer Science 14(1981), pp. 227–246) posed the problem of producing the language L_n = {ab: 1≤a,b≤n and a≠b} with a minimal number of productions. Later, W. Bucher, K. Culik II and H. Maurer showed that $2n + O(n^{12})$ productions are sufficient. In this note we show that $2n + ?2n^{12} ?$ productions are necessary for all n≥ 6.

Keywords:
本文献已被 ScienceDirect 等数据库收录！