k-Queue Automaton



Step     of


Final Decision:

Path-local Decision:




Both deterministic and nondeterministic variants of a one-way multi-queue counter automaton can accept all regular languages.
  • Although their stack alphabet is limited, they still have auxiliary memory, making them more powerful than finite-state accepters.
Both deterministic and nondeterministic variants of a one-way multi-queue counter automaton can recognize some context-free languages but fail to recognize some.
  • The context-free languages that they can recognize include:
    • {ω ∈ (a ∪ b)* | aˣbˣ, x ≥ 0}
    • {ω ∈ (a ∪ b)* | N(a) = N(b)}
  • The context-free languages that they cannot recognize include:
    • {ω ∈ (H ∪ A)* | ωωᴿ}
Both deterministic and nondeterministic variants of a one-way deterministic multi-queue counter queue automaton can recognize some (i.e., but not all) context-sensitive languages.
  • The context-sensitive languages that they can recognize include:
    • {ω ∈ (a ∪ b ∪ c)* | aˣbˣcˣ, x ≥ 0}

A two-way deterministic free-tape single-queue automaton (1‑Queue‑2DQA‑Free-Tape) is equivalent in power to a Turing machine (Ordinary‑TM).

  • We prove the tighter result that a Turing machine can be simulated with a one-way deterministic free-tape single-queue automaton.
  • Our key idea is to establish a bijection between the contents of the tape of MOrdinary‑TM and the queue of M1‑Queue‑2DQA‑Free-Tape via the following strategy:
    • Use a special symbol ⬤ that is not part of the tape alphabet to mark the start of the simulated tape.
    • The symbol to which the tape head of MOrdinary‑TM points is the front of the queue. Symbols on the right of the tape head are in front of ⬤, while symbols on the left of the tape head are behind ⬤.
    • To illustrate, suppose we have the following snapshot of MOrdinary‑TM's tape:

      # a ... b c ...
    • The equivalent snapshot of the queue is as follows:

      b c ... ⬤ # a ...
  • Simulating the MOrdinary‑TM instruction "read symbol d, write symbol b, and move right" is straightforward:
    • Dequeue symbol d, then enqueue symbol b.
    • To illustrate, consider these tape and queue snapshots before executing this instruction:

      a b c d e ...
      d e ... ⬤ a b c
    • After reading symbol d, writing symbol b, and moving right, the tape snapshot is as follows:

      a b c b e ...
    • After dequeueing symbol b and enqueueing symbol b (following our proposed simulation), the queue snapshot is as follows:

      e ... ⬤ a b c b
  • Simulating the MOrdinary‑TM instruction "read symbol d, write symbol b, and move left" is more involved:
    • Introduce the primitive operation Cyclic-Shift whose goal is to transfer a symbol at the back of the queue to the front:
      • Suppose the queue snapshot is as follows:

        e f ⬤ a
      • Enqueue a special symbol ☆ that is not part of the tape alphabet.

        e f ⬤ a ☆
      • Replace each symbol x with a new symbol xy where y is the symbol immediately behind x in the queue.
        • This can be done by using a special state qx to remember that we dequeued x. When the machine encounters y from this state, it will enqueue xy.
        • We keep doing this until we scan the marker ☆, at which point we enqueue ☆ then the symbol that used to be in front of it.
        • In other words, we are using the states as some form of "memory," which works since the tape alphabet is finite.

        ef f⬤ ⬤a ☆ a
      • Afterwards, dequeue the symbols and enqueue only their first characters until the marker ☆ is scanned.

        ☆ a e f ⬤
      • Dequeue ☆ to complete the Cyclic-Shift operation.

        a e f ⬤
    • The instruction "read symbol d, write symbol b, and move left" can then be simulated as follows:
      • Dequeue d, enqueue b, and perform two Cyclic-Shift operations.
      • To illustrate, consider these tape and queue snapshots before executing this instruction:

        a b c d e ...
        d e ... ⬤ a b c
      • After reading symbol d, writing symbol b, and moving left, the tape snapshot is as follows:

        a b c b e ...
      • After dequeueing d, enqueueing b, and performing two Cyclic-Shift operations, the queue snapshot is as follows:

        e ... ⬤ a b c
        e ... ⬤ a b c b
        b e ... ⬤ a b c
        c b e ... ⬤ a b

  • Our key idea is to simulate the queue automaton using two tapes:
    • The first tape serves as an immutable storage for the input string.
    • The second tape is for simulating the queue operations.
      • This can be done in a variety of ways. Perhaps, th simplest way to simulate the dequeueing of a symbol is to to lazily mark it as deleted using a symbol that is not part of the queue alphabet.
  • Since a multi-tape Turing machine is equivalent in power to an ordinary (single-tape) Turing machine, our proof is completed. You may refer to the addendum in our Turing machine page for the sketch of the conversion from multi-tape to single-tape Turing machine.

A two-way nondeterministic free-tape single-queue automaton (1‑Queue‑2NQA‑Free-Tape) is equivalent in power to a Turing machine (Ordinary‑TM).

  • Our key idea is to simulate the automaton using three tapes:
    • The first tape serves as an immutable storage for the input string.
    • The second tape is for simulating the queue operations.
    • The third tape marks the address of the configuration executed by the multi-tape Turing machine in the computational tree of M1‑Queue‑2NQA‑Free-Tape.
    • The nodes of the computational tree of M1‑Queue‑2NQA‑Free-Tape should be visited in a breadth-first fashion. Visiting them in a depth-first fashion risks trapping the machine in a nonterminating branch.
  • Since a multi-tape Turing machine is equivalent in power to an ordinary (single-tape) Turing machine, our sketch is completed. You may refer to the addendum in our Turing machine page for the sketch of the conversion from multi-tape to single-tape Turing machine.

  • Since M1‑Queue‑2DQA‑Free-Tape ⊆ M1‑Queue‑2NQA‑Free-Tape and we have already established that M1‑Queue‑2DQA‑Free-Tape = MOrdinary‑TM, it follows that MOrdinary‑TM ⊆ M1‑Queue‑2DQA‑Free-Tape