RAIRO - Theoretical Informatics and Applications

Table of Contents - May 1999 - Volume 33, Issue 03  

Research Article

There is no complete axiom system for shuffle expressions

Szepietowski, A.

Mathematical Institute, University of Gdańsk, ul. Wita Stwosza 57, 80-952 Gdańsk, Po land; matszp@halina.univ.gda.pl.

Abstract

In this paper we show that neither the set of all valid equations between shuffle expressions nor the set of schemas of valid equations is recursively enumerable. Thus, neither of the sets can be recursively generated by any axiom system.

(Received January 1999)

(Accepted March 1999)

(Online publication August 15 2002)

Mathematics Subject Classification:

  • 68Q45