@article{VOLGER1983333,
    Abstract = {L. Berman [1] has proved completeness results for the theories Th(R, +, 0) and Th(N, +, 0) in time classes with linear alternation. These results exemplify the following phenomenon: A lower bound result of NTIME(t(n)) and an upper bound result of DSPACE(t(n)) for the decision problem of a first order theory T are likely to yield a completeness result for the intermediate class with linear alternation LATIME(t(n)) (=STA(-,t(n),n) in the notation of Berman [1]). We shall prove that the theory BCT(2∗| (n) of t-bounded concatenation is complete in the class LATIME(t(O(n))), whenever t satisfies: t(1)⩾2 and t(m1 + m2)⩾t(m1) · t(m2) for m1, m2 > 0. This yields a sequence of theories which are complete in the classes of the intermediate hierarchy of elementary recursive sets based on time classes with linear alternation. In particular, we shall show that the theory Th(2∗, r0, r1) of the binary tree is complete in LATIME(2O(n)). Two further examples will be provided.},
    Author = {Volger, Hugo},
    File = {Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories - 1-s2.0-0304397583900385-main.pdf},
    ISSN = {0304-3975},
    Journal = {Theoretical Computer Science},
    Number = {3},
    Pages = {333-337},
    Title = {Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories},
    URL = {https://www.sciencedirect.com/science/article/pii/0304397583900385},
    Volume = {23},
    Year = {1983},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/0304397583900385},
    bdsk-url-2 = {https://doi.org/10.1016/0304-3975(83)90038-5},
    date-added = {2022-01-06 08:36:50 +0100},
    date-modified = {2022-01-06 08:36:50 +0100},
    doi = {10.1016/0304-3975(83)90038-5}
}

@article{VOLGER1983333, Abstract = {L. Berman [1] has proved completeness results for the theories Th(R, +, 0) and Th(N, +, 0) in time classes with linear alternation. These results exemplify the following phenomenon: A lower bound result of NTIME(t(n)) and an upper bound result of DSPACE(t(n)) for the decision problem of a first order theory T are likely to yield a completeness result for the intermediate class with linear alternation LATIME(t(n)) (=STA(-,t(n),n) in the notation of Berman [1]). We shall prove that the theory BCT(2∗| (n) of t-bounded concatenation is complete in the class LATIME(t(O(n))), whenever t satisfies: t(1)⩾2 and t(m1 + m2)⩾t(m1) · t(m2) for m1, m2 > 0. This yields a sequence of theories which are complete in the classes of the intermediate hierarchy of elementary recursive sets based on time classes with linear alternation. In particular, we shall show that the theory Th(2∗, r0, r1) of the binary tree is complete in LATIME(2O(n)). Two further examples will be provided.}, Author = {Volger, Hugo}, File = {Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories - 1-s2.0-0304397583900385-main.pdf}, ISSN = {0304-3975}, Journal = {Theoretical Computer Science}, Number = {3}, Pages = {333-337}, Title = {Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories}, URL = {https://www.sciencedirect.com/science/article/pii/0304397583900385}, Volume = {23}, Year = {1983}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/0304397583900385}, bdsk-url-2 = {https://doi.org/10.1016/0304-3975(83)90038-5}, date-added = {2022-01-06 08:36:50 +0100}, date-modified = {2022-01-06 08:36:50 +0100}, doi = {10.1016/0304-3975(83)90038-5} }