主題
Search

量詞消去


量詞消去是從量化系統中移除所有量詞全稱量詞  forall 存在量詞  exists )。如果對於每個量化公式,都存在一個等效的無量詞公式,則一階理論允許量詞消去。 這些理論的例子包括帶有 +*=> 的實數理論,以及帶有 +*= 的複數理論。 量詞消去在以下工具中實現為解決[expr]。

不幸的是,實數量詞消去的在最壞情況下的時間複雜度是量詞塊數量的雙重指數級(Weispfenning 1988,Davenport 和 Heintz 1988,Heintz et al. 1989,Caviness 和 Johnson 1998)。


另請參閱

柱形代數分解存在量詞量詞塔斯基定理全稱量詞

使用 探索

參考資料

Caviness, B. F. 和 Johnson, J. R. (編輯). 量詞消去與柱形代數分解。 紐約:Springer-Verlag,1998 年。Collins, G. E. “透過柱形代數分解對實閉域進行量詞消去。” 在第二屆 GI 計算機自動機理論與形式語言會議論文集中。紐約:Springer-Verlag,第 134-183 頁,1975 年。Collins, G. E. “透過柱形代數分解進行量詞消去——二十年的進展。” 在量詞消去與柱形代數分解(B. F. Caviness 和 J. R. Johnson 編輯)中。紐約:Springer-Verlag,第 8-23 頁,1998 年。Collins, G. E. 和 Hong, H. “用於量詞消去的部分柱形代數分解。” J. Symb. Comput. 12, 299-328, 1991 年。Davenport, J. H. “柱形代數分解的計算機代數。” 報告 TRITA-NA-8511,NADA,KTH,斯德哥爾摩,1985 年 9 月。Davenport, J. 和 Heintz, J. “實數量詞消去是雙重指數級的。” J. Symb. Comput. 5, 29-35, 1988 年。Dolzmann, A. 和 Sturm, T. “有序域上無量詞公式的簡化。” J. Symb. Comput. 24, 209-231, 1997 年。Dolzmann, A. 和 Weispfenning, V. “區域性量詞消去。” http://www.fmi.uni-passau.de/~dolzmann/refs/MIP-0003.ps.ZHeintz, J.; Roy, R.-F.; 和 Solerno, P. “Tarski-Seidenberg 原理的複雜度。” C. R. Acad. Sci. Paris Sér. I Math. 309, 825-830, 1989 年。Loos, R. 和 Weispfenning, V. “應用格量詞消去。” Comput. J. 36, 450-461, 1993 年。Strzebonski, A. “求解代數不等式。” Mathematica J. 7, 525-541, 2000 年。Weispfenning, V. “域中線性問題的複雜度。” J. Symb. Comput. 5, 3-27, 1988 年。

在 中被引用

量詞消去

引用為

Weisstein, Eric W. “量詞消去”。來自 ——Wolfram 網路資源。 https://mathworld.tw/QuantifierElimination.html

主題分類