《具有較小空間複雜性的交替式下推自動機的研究》是依託中國海洋大學，由徐建良擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：具有較小空間複雜性的交替式下推自動機的研究
- 項目類別：青年科學基金項目
- 項目負責人：徐建良
- 依託單位：中國海洋大學
- 批准號：60403012
- 申請代碼：F0201
- 負責人職稱：教授
- 研究期限：2005-01-01 至 2007-12-31
- 支持經費：22（萬元）
中文摘要
研究具有較小空間複雜性的交替式下推自動機是非常有意義的，因為交替式下推自動機是一個比交替式圖靈機更簡單的並行計算模型，它的性質解明對於並行計算機的計算複雜性的研究具有重要意義，很有研究價值。但是關於具有較小空間複雜性的交替式下推自動機的研究在國際和國內都還比較少。本項目將研究兩種下推自動機：交替式下推自動機和具有墨水點的交替式下推自動機。我們將圍繞亞對數空間和亞線性空間對這兩種計算模型的性質展開研究，主要研究內容包括：具有較小空間複雜性的語言族的閉包性的研究、空間複雜性的階層性的研究、交替深度和交替總量之間的關係以及交替總量的階層性的研究、具有一個墨水點的交替式下推自動機的基本性質的研究、具有一個墨水點的交替式下推自動機的交替階層性的研究以及墨水點個數的階層性問題的研究。
