亚对数空间限定多墨水点交替式下推自动机的计算复杂性
图书信息
书名：亚对数空间限定多墨水点交替式下推自动机的计算复杂性作者：王建良
包装：平装
开本：16
出版社：科学技术文献出版社
出版时间：2020-09-01
图书简介
交替式下推自动机是当前并行与分布式计算环境的数学模型，而墨水点是对移动智能体在宿主机器上写入信息的一种模拟。本书研究了具有亚对数空间的2方向交替式下推自动机和具有多个墨水点的交替式下推自动机，并对这两种类型自动机模型的一些重要性质进行了深入研究。研究了在亚对数空间下，墨水点个数对仅有全称状态的多墨水点交替式下推自动机计算能力的影响，证明了亚对数空间限定的仅有全称状态的多墨水点交替式下推自动机计算能力随着墨水点个数的增加而增强。同时，论证了在亚对数空间下，仅有全称状态和仅有存在状态的多墨水点交替式下推自动机计算能力的关系，证明了它们的计算能力是不可比较的。最后引入自验证的1墨水点2方向非确定性下推自动机，并证明了在亚对数空间下，具有1墨水点的非确定性下推自动机计算能力比具有1墨水点的自验证非确定性下推自动机的计算能力强。本书为研究交替式下推自动机和墨水点问题的学者提供了深入且有用的信息。
推荐理由
相信对计算机科学有所涉猎的读者都知道，交替式下推自动机是一种重要的数学模型。而在这些模型中，墨水点问题更是如此。本书深入研究了这些问题，提供了宝贵的理论借鉴，同时也对读者进行认知启发。如果你对计算机科学感兴趣，本书将是一本非常好的选择。
