Hostname: page-component-7b7567c8c-p67k6 Total loading time: 0 Render date: 2026-11-19T11:29:14.510Z Has data issue: false hasContentIssue false

Axiomatizing omega and omega-op powersof words

Published online by Cambridge University Press:  15 March 2004

Stephen L. Bloom
Affiliation:
Department of Computer Science Stevens Institute of Technology Hoboken, NJ 07030; bloom@cs.stevens-tech.edu.
Zoltán Ésik
Affiliation:
Institute for Informatics University of Szeged 6720 Szeged, Hungary
Get access

Abstract

In 1978, Courcelle asked for a completeset of axioms and rules for the equational theory of (discrete regular) words equipped with the operations of product, omega power and omega-op power. In this paper we find a simple set of equationsand prove they are complete.Moreover, we show that the equational theory is decidable in polynomial time.

Keywords

Information

Type
Research Article
Copyright
© EDP Sciences, 2004

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.)

Article purchase

Temporarily unavailable