License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2015.241
URN: urn:nbn:de:0030-drops-52006
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5200/
Go to the corresponding LIPIcs Volume Portal

Kotsireas, Ilias ; Kutsia, Temur ; Simos, Dimitris E.

Constructing Orthogonal Designs in Powers of Two: Gröbner Bases Meet Equational Unification

pdf-format:
20.pdf (0.5 MB)

Abstract

In the past few decades, design theory has grown to encompass a wide variety of research directions. It comes as no surprise that applications in coding theory and communications continue to arise,
and also that designs have found applications in new areas. Computer science has provided a new source of applications of designs, and simultaneously a field of new and challenging problems in design theory. In this paper, we revisit a construction for orthogonal designs using the multiplication tables of Cayley-Dickson algebras of dimension $2^n$. The desired orthogonal designs can be described by a system of equations with the aid of a Groebner basis computation. For orders greater than 16 the combinatorial explosion of the problem gives rise to equations that are unfeasible to be handled by traditional search algorithms. However, the structural properties of the designs make this problem possible to be tackled in terms of rewriting techniques, by equational unification. We establish connections between central concepts of design theory and equational unification where equivalence operations of designs point to the computation of a minimal complete set of unifiers. These connections make viable the computation of some types of orthogonal designs that have not been found before with the aforementioned algebraic modelling.

BibTeX - Entry

@InProceedings{kotsireas_et_al:LIPIcs:2015:5200,
  author =	{Ilias Kotsireas and Temur Kutsia and Dimitris E. Simos},
  title =	{{Constructing Orthogonal Designs in Powers of Two: Gr{\"o}bner Bases Meet Equational Unification}},
  booktitle =	{26th International Conference on Rewriting Techniques and Applications (RTA 2015)},
  pages =	{241--256},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-85-9},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{36},
  editor =	{Maribel Fern{\'a}ndez},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5200},
  URN =		{urn:nbn:de:0030-drops-52006},
  doi =		{10.4230/LIPIcs.RTA.2015.241},
  annote =	{Keywords: Orthogonal designs, unification theory, algorithms, Groebner bases}
}

Keywords: Orthogonal designs, unification theory, algorithms, Groebner bases
Collection: 26th International Conference on Rewriting Techniques and Applications (RTA 2015)
Issue Date: 2015
Date of publication: 18.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI