The pseudopalindromic completion of regular languages

被引：4

作者：

Fazekas, Szilard Zsolt ^{[1
]}

Manea, Florin ^{[2
]}

Mercas, Robert ^{[2
]}

Shikishima-Tsuji, Kayoko ^{[3
]}

机构：

[1] Akita Univ, Dept Comp Sci & Engn, Akita 0108502, Japan

[2] Univ Kiel, Dept Comp Sci, D-24098 Kiel, Germany

[3] Tenri Univ, Tenri, Nara 6328510, Japan

来源：

INFORMATION AND COMPUTATION | 2014年 / 239卷

关键词：

Pseudopalindromes; Pseudopalindromic completion; Pseudopalindromic iterated completion; Regular languages; Algorithms; Decidability; HAIRPIN COMPLETION;

D O I：

10.1016/j.ic.2014.09.001

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Pseudopalindromes are words that are fixed points for some antimorphic involution. In this paper we discuss a newer word operation, that of pseudopalindromic completion, in which symbols are added to either side of the word such that the new obtained words are pseudopalindromes. This notion represents a particular type of hairpin completion, where the length of the hairpin is at most one. We give precise descriptions of regular languages that are closed under this operation and show that the regularity of the closure under the operation is decidable. (C) 2014 Elsevier Inc. All rights reserved.

引用

页码：222 / 236

页数：15

共 22 条

[1]

[Anonymous], 1997, ACM SIGACT NEWS

[2]

Cheptea D., 2006, Proc. Transgressive Computing, P216

[3] Pseudopalindrome closure operators in free monoids [J].

de Luca, Aldo ;

De Luca, Alessandro .

THEORETICAL COMPUTER SCIENCE, 2006, 362 (1-3) :282-300

[4] Sturmian words: structure, combinatorics, and their arithmetics [J].

deLuca, A .

THEORETICAL COMPUTER SCIENCE, 1997, 183 (01) :45-82

[5]

Diekert V, 2009, LECT NOTES COMPUT SC, V5684, P170, DOI 10.1007/978-3-642-03466-4_11

[6]

Fazekas SZ, 2012, LECT NOTES COMPUT SC, V7410, P428, DOI 10.1007/978-3-642-31653-1_38

[7]

HARRISON M, 1978, INTRO FORMAL LANGUAG

[8]

Holzer M., 2003, International Journal of Foundations of Computer Science, V14, P1087, DOI 10.1142/S0129054103002199

[9]

Horvath S., 1987, Journal of Information Processing and Cybernetics, V23, P441

[10] Bounded hairpin completion [J].

Ito, Masami ;

Leupold, Peter ;

Manea, Florin ;

Mitrana, Victor .

INFORMATION AND COMPUTATION, 2011, 209 (03) :471-485

← 1 2 3 →