Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
type: Item
instance of: scholarly article
title: Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
zbMATH Open document ID: 0538.03035
DOI: 10.1016/0304-3975(83)90038-5
author: Hugo Volger
published in: Theoretical Computer Science
publication date: 1983-01-01T00:00:00Z
review text: A language L belongs to the complexity class \(LATIME(t(n))\) if it is accepted by some alternating Turing machine M which on inputs of length n makes at most t(n) steps and involves at most n alternations. For \(\Sigma\) a finite alphabet \(BCT(\Sigma^*| t(n))\) is the theory of the structure \((\Sigma^*,Con(t(n)))_{n\in N}\) where Con(t(n)) denotes the concatenation relation on \(\{w\in \Sigma^*| \quad | w| \leq t(n)\}.\) The author states without proof that \(BCT(\{0,1\}^*| t(n))\) (and some variants) are complete in \(LATIME(t(0(n)))\) with respect to polynomial time reductions whenever t satisfies \(t(m_ 1+m_ 2)\geq t(m_ 1)\cdot t(m_ 2)\) for \(m_ 1,m_ 2>0\) and t(1)\(\geq 2\).
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 03B25
zbMATH DE Number: 3855085
zbMATH Keywords: bounded concatenation
zbMATH Keywords: decision problem of first order theories
zbMATH Keywords: complexity class
zbMATH Keywords: alternating Turing machine
reviewed by: J. M. Plotkin
MaRDI profile type: Publication
full work available at URL: 0304-3975(83)90038-5
OpenAlex ID: W1995317845
cites work: The complexity of logical theories
cites work: On Languages Accepted in Polynomial Time
cites work: On time-space classes and their relation to the theory of real addition
cites work: Alternation
cites work: The computational complexity of logical theories
cites work: Q4082296
cites work: Q3880807
cites work: Complexity of Boolean algebras
cites work: Q3949037
cites work: The polynomial-time hierarchy
cites work: Q4131648
description: scientific article; zbMATH DE number 3855085