Forkable Regular Expressions

被引：4

作者：

Sulzmann, Martin ^{[1
]}

Thiemann, Peter ^{[2
]}

机构：

[1] Karlsruhe Univ Appl Sci, Fac Comp Sci & Business Informat Syst, Moltkestr 30, D-76133 Karlsruhe, Germany

[2] Univ Freiburg, Fac Engn, Georges Kohler Allee 079, D-79110 Freiburg, Germany

来源：

LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS, LATA 2016 | 2016年 / 9618卷

关键词：

Automata and logic; Forkable expressions; Derivatives; ITERATED SHUFFLE; PETRI NETS;

D O I：

10.1007/978-3-319-30000-9_15

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We consider forkable regular expressions, which enrich regular expressions with a fork operator, to establish a formal basis for static and dynamic analysis of the communication behavior of concurrent programs. We define a novel compositional semantics for forkable expressions, establish their fundamental properties, and define derivatives for them as a basis for the generation of automata, for matching, and for language containment tests. Forkable expressions may give rise to non-regular languages, in general, but we identify sufficient conditions on expressions that guarantee finiteness of the automata construction via derivatives.

引用

页码：194 / 206

页数：13

共 14 条

[1] Amtoft T., 1998, SOFTWARE TOOLS TECHN, V2, P13
[2] [Anonymous], J FUNCTIONAL PROGRAM
[3] DERIVATIVES OF REGULAR EXPRESSIONS
BRZOZOWSKI, JA
[J]. JOURNAL OF THE ACM, 1964, 11 (04) : 481 - &
[4] CONCURRENT REGULAR EXPRESSIONS AND THEIR RELATIONSHIP TO PETRI NETS
GARG, VK
RAGUNATH, MT
[J]. THEORETICAL COMPUTER SCIENCE, 1992, 96 (02) : 285 - 304
[5] Ginsburg S., 1966, The mathematical theory of context-free languages
[6] SHUFFLE LANGUAGES, PETRI NETS, AND CONTEXT-SENSITIVE GRAMMARS
GISCHER, J
[J]. COMMUNICATIONS OF THE ACM, 1981, 24 (09) : 597 - 605
[7] EXTENDING REGULAR EXPRESSIONS WITH ITERATED SHUFFLE
JANTZEN, M
[J]. THEORETICAL COMPUTER SCIENCE, 1985, 38 (2-3) : 223 - 247
[8] NESTING OF SHUFFLE CLOSURE IS IMPORTANT
JEDRZEJOWICZ, J
[J]. INFORMATION PROCESSING LETTERS, 1987, 25 (06) : 363 - 367
[9] KOZEN D, 1990, LECT NOTES COMPUT SC, V452, P26
[10] LEISS H, 1991, LNCS, V626, P242

← 1 2 →