On the structure of graphs in the Caucal hierarchy
On the structure of graphs in the Caucal hierarchy
复制标题
关于 Caucal 层次结构中的图结构
DOI：
10.1016/j.tcs.2008.01.053
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Achim Blumensath
中科院分区：
文献类型：
--
作者：
Achim Blumensath
我们调查的结构图中的高加索层次结构。我们提供的标准有关的程度的顶点或长度的路径，可以用来表明，一个给定的图不属于这个层次的某个级别。Caucal层次中的每个图对应于某个高阶下推自动机的配置图。本文的主要部分包括这样的配置图的研究。我们提供了工具来分解和重组他们的运行，我们证明了一个泵引理高阶下推自动机。
We investigate the structure of graphs in the Caucal hierarchy. We provide criteria concerning the degree of vertices or the length of paths which can be used to show that a given graph does not belong to a certain level of this hierarchy. Each graph in the Caucal hierarchy corresponds to the configuration graph of some higher-order pushdown automaton. The main part of the paper consists of a study of such configuration graphs. We provide tools to decompose and reassemble their runs, and we prove a pumping lemma for higher-order pushdown automata.
登录
查看更多内容
DOI：
10.1007/3-540-36387-4_16
发表时间：
2001
影响因子：
1.2
作者：
Dietmar Berwanger;Achim Blumensath
通讯作者：
Achim Blumensath
树状结构上的一元二阶逻辑
DOI：
10.1016/s0304-3975(01)00185-2
发表时间：
2002
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
I. Walukiewicz
通讯作者：
I. Walukiewicz
影响因子：
--
作者：
DAMM, W;GOERDT, A
通讯作者：
GOERDT, A
一元理论的可判定性
DOI：
10.1007/bfb0030296
发表时间：
1984
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Alexei L. Semenov
通讯作者：
Alexei L. Semenov
在无限项上具有可判定的一元理论
DOI：
10.1007/3-540-45687-2_13
发表时间：
2002
期刊：
2008 23rd Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
D. Caucal
通讯作者：
D. Caucal