Ambiguity of the Multiple Interpretations on Regular Languages

被引：0

作者：

Pablo Alarcon, Pedro ^{[1
]}

Arroyo, Fernando ^{[2
]}

Bordihn, Henning ^{[3
]}

Mitrana, Victor ^{[1
]}

Mueller, Mike ^{[4
]}

机构：

[1] Univ Politecn Madrid, Dept Org & Struct Informat, Madrid 28031, Spain

[2] Univ Politecn Madrid, Dept Languages Projects & Comp Informat Syst, Madrid 28031, Spain

[3] Univ Potsdam, Dept Comp Sci, D-14482 Potsdam, Germany

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

来源：

FUNDAMENTA INFORMATICAE | 2015年 / 138卷 / 1-2期

关键词：

Multiple interpretation scheme; regular language; o-ambiguity; internal ambiguity; external ambiguity; PATTERN LANGUAGES;

D O I：

10.3233/FI-2015-1200

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

A multiple interpretation scheme is an ordered sequence of morphisms. The ordered multiple interpretation of a word is obtained by concatenating the images of that word in the given order of morphisms. The arbitrary multiple interpretation of a word is the semigroup generated by the images of that word. These interpretations are naturally extended to languages. Four types of ambiguity of multiple interpretation schemata on a language are defined: o-ambiguity, internal ambiguity, weakly external ambiguity and strongly external ambiguity. We investigate the problem of deciding whether a multiple interpretation scheme is ambiguous on regular languages.

引用

页码：85 / 95

页数：11

共 15 条

[1] FINDING PATTERNS COMMON TO A SET OF STRINGS
ANGLUIN, D
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1980, 21 (01) : 46 - 62
[2] File G., 1988, LECT NOTES COMPUTER, V294, P184
[3] Herman G.T., 1975, Developmental Systems and Languages
[4] PATTERN LANGUAGES WITH AND WITHOUT ERASING
JIANG, T
KINBER, E
SALOMAA, A
SALOMAA, K
YU, S
[J]. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1994, 50 (3-4) : 147 - 163
[5] A NOTE ON THE SPACE COMPLEXITY OF SOME DECISION-PROBLEMS FOR FINITE AUTOMATA
JIANG, T
RAVIKUMAR, B
[J]. INFORMATION PROCESSING LETTERS, 1991, 40 (01) : 25 - 31
[6] Karhumaki J., 1991, LECT NOTES COMPUTER, V520, P249
[7] MULTI-PATTERN LANGUAGES
KARI, L
MATEESCU, A
PAUN, G
SALOMAA, A
[J]. THEORETICAL COMPUTER SCIENCE, 1995, 141 (1-2) : 253 - 268
[8] Kudlek M., 2002, Grammars, V5, P223, DOI 10.1023/A:1022175314408
[9] INHERENT AMBIGUITY OF SIMPLE TUPLE LANGUAGES
KUICH, W
MAURER, H
[J]. COMPUTING, 1971, 7 (3-4) : 194 - &
[10] Langton C., 1989, SANTA FE I STUDIES S

← 1 2 →