Nonassociative structures on polynomial algebras arising from bio-operations on formal languages: an application of computer algebra to nonassociative systems

ABSTRACT

We consider sequential insertion and deletion, and contextual insertion and deletion, on the free monoid Σ where Σ = {x}; in each case the result can be regarded as either a set or a multiset. Over any coefficient field F the vector space with basis Σ* is linearly isomorphic to the polynomial algebra F[x]; each operation on Σ* extends bilinearly to give a new algebra structure (not necessarily commutative or associative) on F[x]. We determine the polynomial identities of degree ≤ 5 satisfied by these structures.

REFERENCES

• 1: M. R. Bremner. DNA computing, insertion of words and left-symmetric algebras. Proceedings of Maple Conference 2005 (July 17-20, 2005, Waterloo, Ontario, Canada), edited by Ilias S. Kotsireas, Waterloo Maple, 2005, pages 229--242.
• 2: Murray R. Bremner, Jordan algebras arising from intermolecular recombination, ACM SIGSAM Bulletin, v.39 n.4, December 2005 [doi>10.1145/1140378.1140380]
• 3: M. R. Bremner, Lúcia I. Murakami and I. P. Shestakov. Nonassociative algebras. Handbook of Linear Algebra, edited by Leslie Hogben, Chapman & Hall / CRC, Boca Raton, 2006, pages 69--1 to 69--26.
• 4: George E. Collins , Mark J. Encarnación, Efficient rational number reconstruction, Journal of Symbolic Computation, v.20 n.3, p.287-297, Sept. 1995 [doi>10.1006/jsco.1995.1051]
• 5: A. Dzhumadildaev and C. Löfwall. Trees, free right-symmetric algebras, free Novikov algebras and identities. Homology Homotopy and Applications 4 (2002) 165--190 (electronic).
• 6: J.-C. Faugère. A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra 139 (1999) 61--88.
• 7: Lila Kari. On Insertion and Deletion in Formal Languages. Ph.D. Dissertation, Department of Mathematics, University of Turku, Finland, 1991.
• 8: J. M. Osborn and E. Zelmanov. Nonassociative algebras related to Hamiltonian operators in the formal calculus of variations. Journal of Pure and Applied Algebra 101 (1995) 335--352.
• 9: G. Pǎun, G. Rozenberg and A. Salomaa. DNA Computing: New Computing Paradigms. Springer-Verlag, New York, 1998.
• 10: K. A. Zhevlakov, A. M. Slinko, I. P. Shestakov and A. I. Shirshov. Rings that are Nearly Associative. Academic Press, New York, 1982.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Algebraic language theory

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Mathematics and statistics
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms, Languages, Theory

Keywords:
DNA computing, bio-operations, computer algebra, finite fields, formal languages, linear systems, nonassociative algebra, polynomial identities