Determining when the absolute state complexity of a Hermitian code achieves its DLP bound

Blackmore, T and Norton, GH (2002) Determining when the absolute state complexity of a Hermitian code achieves its DLP bound. Siam Journal On Discrete Mathematics, 15 1: 14-40. doi:10.1137/S0895480100376435

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
UQ61194_OA.pdf Full text (open access) application/pdf 309.52KB 0

Author Blackmore, T
Norton, GH
Title Determining when the absolute state complexity of a Hermitian code achieves its DLP bound
Journal name Siam Journal On Discrete Mathematics   Check publisher's open access policy
ISSN 0895-4801
Publication date 2002
Sub-type Article (original research)
DOI 10.1137/S0895480100376435
Open Access Status File (Publisher version)
Volume 15
Issue 1
Start page 14
End page 40
Total pages 27
Editor D. Shmoys
Place of publication Philadelphia, PA, United States
Publisher Society for Industrial and Applied Mathematics
Collection year 2002
Language eng
Abstract Let g be the genus of the Hermitian function field H/F(q)2 and let C-L(D,mQ(infinity)) be a typical Hermitian code of length n. In [Des. Codes Cryptogr., to appear], we determined the dimension/length profile (DLP) lower bound on the state complexity of C-L(D,mQ(infinity)). Here we determine when this lower bound is tight and when it is not. For m less than or equal to n-2/2 or m greater than or equal to n-2/2 + 2g, the DLP lower bounds reach Wolf's upper bound on state complexity and thus are trivially tight. We begin by showing that for about half of the remaining values of m the DLP bounds cannot be tight. In these cases, we give a lower bound on the absolute state complexity of C-L(D,mQ(infinity)), which improves the DLP lower bound. Next we give a good coordinate order for C-L(D,mQ(infinity)). With this good order, the state complexity of C-L(D,mQ(infinity)) achieves its DLP bound (whenever this is possible). This coordinate order also provides an upper bound on the absolute state complexity of C-L(D,mQ(infinity)) (for those values of m for which the DLP bounds cannot be tight). Our bounds on absolute state complexity do not meet for some of these values of m, and this leaves open the question whether our coordinate order is best possible in these cases. A straightforward application of these results is that if C-L(D,mQ(infinity)) is self-dual, then its state complexity (with respect to the lexicographic coordinate order) achieves its DLP bound of n /2 - q(2)/4, and, in particular, so does its absolute state complexity.
Keyword Mathematics, Applied
Hermitian Code
State Complexity
Dimension/length Profile Bound
Geometric Goppa Codes
Trellis Complexity
Weight Hierarchy
Q-Index Code C1

Document type: Journal Article
Sub-type: Article (original research)
Collection: School of Physical Sciences Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 1 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 14 Aug 2007, 17:02:24 EST