Blog
About

8
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Variations of Checking Stack Automata: Obtaining Unexpected Decidability Properties

      Preprint

      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We introduce a model of one-way language acceptors (a variant of a checking stack automaton) and show the following decidability properties: (1) The deterministic version has a decidable membership problem but has an undecidable emptiness problem. (2) The nondeterministic version has an undecidable membership problem and emptiness problem. There are many models of accepting devices for which there is no difference with these problems between deterministic and nondeterministic versions, i.e., the membership problem for both versions are either decidable or undecidable, and the same holds for the emptiness problem. As far as we know, the model we introduce above is the first one-way model to exhibit properties (1) and (2). We define another family of one-way acceptors where the nondeterministic version has an undecidable emptiness problem, but the deterministic version has a decidable emptiness problem. We also know of no other model with this property in the literature. We also investigate decidability properties of other variations of checking stack automata (e.g., allowing multiple stacks, two-way input, etc.). Surprisingly, two-way deterministic machines with multiple checking stacks and multiple reversal-bounded counters are shown to have a decidable membership problem, a very general model with this property.

          Related collections

          Most cited references 7

          • Record: found
          • Abstract: not found
          • Article: not found

          Reversal-Bounded Multicounter Machines and Their Decision Problems

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Reversal-bounded multipushdown machines

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Some Decision Problems Concerning Semilinearity and Commutation

                Bookmark

                Author and article information

                Journal
                2017-05-26
                Article
                1705.09732

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                17 pages
                cs.FL

                Theoretical computer science

                Comments

                Comment on this article