Axiomatizing omega and omega-op powers of words

被引：8

作者：

Bloom, SL ^{[1
]}

Ésik, Z

机构：

[1] Stevens Inst Technol, Dept Comp Sci, Hoboken, NJ 07030 USA

[2] Univ Szeged, Inst Informat, H-6720 Szeged, Hungary

来源：

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS | 2004年 / 38卷 / 01期

关键词：

D O I：

10.1051/ita:2004005

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In 1978, Courcelle asked for a complete set 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 equations and prove they are complete. Moreover, we show that the equational theory is decidable in polynomial time.

引用

页码：3 / 17

页数：15

共 17 条

[1] Finite automata and ordinals
Bedon, N
[J]. THEORETICAL COMPUTER SCIENCE, 1996, 156 (1-2) : 119 - 144
[2] An Eilenberg theorem for words on countable ordinals
Bedon, N
Carton, O
[J]. LATIN '98: THEORETICAL INFORMATICS, 1998, 1380 : 53 - 64
[3] Bloom SL, 2003, FUND INFORM, V55, P1
[4] Long words:: the theory of concatenation and ω-power
Bloom, SL
Choffrut, C
[J]. THEORETICAL COMPUTER SCIENCE, 2001, 259 (1-2) : 533 - 548
[5] Bloom Stephen L, 1993, Iteration theories
[6] Bruyère V, 2002, INT FED INFO PROC, V96, P107
[7] Bruyère V, 2001, LECT NOTES COMPUT SC, V2136, P236
[8] Buchi J.R., 1960, INT C LOG METH PHIL, P1
[9] BUCHI JR, 1965, INT C LOG METH PHIL, P2
[10] FINITE AUTOMATA, DEFINABLE SETS, AND REGULAR EXPRESSIONS OVER OMEGA-N-TAPES
CHOUEKA, Y
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1978, 17 (01) : 81 - 97

← 1 2 →