Forest-regular languages and tree-regular languages
Forest-regular languages and tree-regular languages
复制标题
森林正则语言和树正则语言
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
M. Murata
中科院分区：
文献类型：
--
作者：
M. Murata
定义2.1(森林)。森林是：(1)(零森林)，(2)ahui，其中a是中的符号，u是森林，或(3)uv，其中u和v是森林。上面的森林集合用F表示。对于任何森林u；v；w 2F；u(Vw)=(Uv)w且u=u=u。我们缩写ah i作为注释。由于abc=ah ibh ich i：：：，字符串也是林。定义2.2(树)。树是阿惠形式的森林。上面的树的集合用T表示。定义2.3(森林宽度)。森林u的宽度，表示为juj，是位于u的顶层的树木的数量。即，j j=0；jahuij=1，juvj=juj+jvj。定义2.4(林区)。我们将F1；2；3；：：：g的子集分配给每个u 2F，表示为Dom(U)，使得：(1)如果u=，则Dom(U)=；，(2)如果u=ahvi，则Dom(U)=f1g[F1 V1V2：：：Vk j k 0；V1V2：：：Vk 2Dom(V)g，
De nition 2.1 (forest). A forest over is: (1) (the null forest), (2) ahui, where a is a symbol in and u is a forest, or (3) uv, where u and v are forests. The set of forests over is denoted by F . For any forest u; v; w 2 F ; u(vw) = (uv)w and u = u = u. We abbreviate ah i as a. Remark. Since abc = ah ibh ich i : : : , a string is also a forest. De nition 2.2 (tree). A tree is a forest of the form ahui. The set of trees over is denoted by T . De nition 2.3 (forest width). The width of a forest u, denoted juj, is the number of trees at the top level of u. That is, j j = 0; jahuij = 1, and juvj = juj+ jvj. De nition 2.4 (forest domain). We assign to each u 2 F a subset of f1; 2; 3; : : :g , denoted Dom(u), such that: (1) if u = , then Dom(u) = ;, (2) if u = ahvi, then Dom(u) = f1g [ f1 v1v2 : : : vk j k 0; v1v2 : : : vk 2 Dom(v)g,