Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-27T08:48:57.572Z Has data issue: false hasContentIssue false
  • English
  • Français

There is no complete axiom systemfor shuffle expressions

Published online by Cambridge University Press:  15 August 2002

A. Szepietowski
A. Szepietowski*
Affiliation:
Mathematical Institute, University of Gdańsk, ul. Wita Stwosza 57, 80-952 Gdańsk, Po land; [email protected].
Get access

Abstract

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

Keywords

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 33 , Issue 3 , May 1999 , pp. 271 - 277
Copyright
© EDP Sciences, 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bloom, S.L. and Ésik, Z., Axiomatizing shuffle and concatenation in languages. Inform. and Comput. 139 (1997) 62-91. CrossRef
Bloom, S.L. and Ésik, Z., Shuffle binoids. Theor. Informatics Appl. 32 (1998) 175-198. CrossRef
J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley (1979).
Iwama, K., The universe problem for unrestricted flow languages. Acta Inform. 19 (1983) 85-96. CrossRef
T. Kimura, An algebraic systems for process structuring and interprocess communication, Proc. 8 Annual Symposium on Theory of Computing (1976) 92-100.
Krob, D., Complete systems of B-rational identities. Theoret. Comput. Sci. 89 (1991) 207-343. CrossRef
A.R. Meyer and A. Rabinovich, A solution of an interleaving decision problem by a partial order techniques, Proc. Workshop on Partial-order Methods in Verification, July 1996, Princeton NJ, Ed. G. Holzmann, D. Peled, V. Pratt, AMS-DIMACS Series in Discrete Math.
A. Salomaa, Theory of Automata, Pergamon Press, Oxford (1969).