Tabulator Turing machine and complexity
Es wird ein \glqq Tabulator-Turingmachine\grqq{} (TTM) genanntes Modell einer Turingmaschine definiert, die mit dem Lesekopf in einem Schritt über mehrere Felder des Bandes auf Marken springen kann, die sie vorher auf das Band gesetzt hat. Dadurch werden Eigenschaften der Turingmaschine (TM) (Beschreibbarkeit durch eine endliche Maschinentafel) und eines realen Computers (Random-Access-Zugriff) miteinander kombiniert und außerdem ein theoretisches Modell für einen Computer mit assoziativer Speicherung angegeben. Die TTM hat die Eigenschaft, daß sich die Komplexität beim Übergang vom Mehrband- zum 1-Band-Modell nur um einen konstanten Faktor erhöht; sie führt auch zu anderen Komplexitätsklassen als die übliche TM-Komplexitätsdefinition nach Hartmanis und Stearns. Der dafür angegebene Beweis enthält einen Fehler, da verschieden definierte Maschinentypen unzulässig miteinander in Beziehung gebracht werden. Die Behauptung läßt sich jedoch für das On-Line-Modell (nach Hennie) einer TM bzw. TTM beweisen, indem man eine Sprache \(L\) angibt, die von einer On-Line-TTM in \(Cn\) Schritten, aber von keiner mehrbändigen On-Line-TM in weniger als \(C' n \sqrt{n}\) Schritten erkannt werden kann. \(L\) ist dabei definiert als die Menge aller Ketten \(w \in\{0,1,2\}^*\), für die es ein \(k\) gibt, so daß gilt: \( w=u_1 2u_2 2 \ldots 2u_k 22x_1 \bar{j}_1 2x_2 \bar{j}_2 2 \ldots 2x_i \bar{j}_1 2\) mit \(u_i, x_i\in\{0,1\}^*\), \(|u_i| = |x_i |= k\) für alle \(i\), \(\bar{j}_i=1^{j_i} 0^{k-j_i}\) mit \(1 \le j \le k\), und mit \(x_1=u_{j_1}\). Schlieblich wird für verschiedene Erkennungsverfahren (Bottom-Up und Top-Down) für kontextfreie Sprachen die Komplexität bei Berechnung durch eine TTM angegeben.
- A note on computing time for recognition of languages generated by linear grammars
- A Syntax-Analysis Procedure for Unambiguous Context-Free Grammars
- An efficient context-free parsing algorithm
- On the Computational Complexity of Algorithms
- On-Line Turing Machine Computations
- Recognition and parsing of context-free languages in time n3
This page was built for publication: Tabulator Turing machine and complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2547888)