@inproceedings{10.1007/3-540-45061-0_56,
    Abstract = {We prove an upper bound result for the first-order theory of a structure W of queues, i.e. words with two relations: addition of a letter on the left and on the right of a word. Using complexity-tailored Ehrenfeucht games we show that the witnesses for quantified variables in this theory can be bound by words of an exponential length. This result, together with a lower bound result for the first-order theory of two successors [6], proves that the first-order theory of W is complete in LATIME(2O(n)): the class of problems solvable by alternating Turing machines runningin exponential time but only with a linear number of alternations.},
    Address = {Berlin, Heidelberg},
    Author = {Rybina, Tatiana and Voronkov, Andrei},
    BookTitle = {Automata, Languages and Programming},
    Editor = {Baeten, Jos C. M. and Lenstra, Jan Karel and Parrow, Joachim and Woeginger, Gerhard J.},
    File = {Upper bounds for a theory of queues - Rybina-Voronkov2003\_Chapter\_UpperBoundsForATheoryOfQueues.pdf},
    ISBN = {978-3-540-45061-0},
    Pages = {714--724},
    Publisher = {Springer Berlin Heidelberg},
    Title = {Upper Bounds for a Theory of Queues},
    Year = {2003},
    date-added = {2022-01-06 09:06:51 +0100},
    date-modified = {2022-01-06 09:06:51 +0100},
    doi = {10.1007/3-540-45061-0_56}
}

@inproceedings{10.1007/3-540-45061-0_56, Abstract = {We prove an upper bound result for the first-order theory of a structure W of queues, i.e. words with two relations: addition of a letter on the left and on the right of a word. Using complexity-tailored Ehrenfeucht games we show that the witnesses for quantified variables in this theory can be bound by words of an exponential length. This result, together with a lower bound result for the first-order theory of two successors [6], proves that the first-order theory of W is complete in LATIME(2O(n)): the class of problems solvable by alternating Turing machines runningin exponential time but only with a linear number of alternations.}, Address = {Berlin, Heidelberg}, Author = {Rybina, Tatiana and Voronkov, Andrei}, BookTitle = {Automata, Languages and Programming}, Editor = {Baeten, Jos C. M. and Lenstra, Jan Karel and Parrow, Joachim and Woeginger, Gerhard J.}, File = {Upper bounds for a theory of queues - Rybina-Voronkov2003_Chapter_UpperBoundsForATheoryOfQueues.pdf}, ISBN = {978-3-540-45061-0}, Pages = {714--724}, Publisher = {Springer Berlin Heidelberg}, Title = {Upper Bounds for a Theory of Queues}, Year = {2003}, date-added = {2022-01-06 09:06:51 +0100}, date-modified = {2022-01-06 09:06:51 +0100}, doi = {10.1007/3-540-45061-0_56} }