Blog
About

2
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: not found

      Space Complexity of Stack Automata Models

      Read this article at

      ScienceOpenPublisherPMC
      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

          This paper examines several measures of space complexity on variants of stack automata: non-erasing stack automata and checking stack automata. These measures capture the minimum stack size required to accept any word in a language (weak measure), the maximum stack size used in any accepting computation on any accepted word (accept measure), and the maximum stack size used in any computation (strong measure). We give a detailed characterization of the accept and strong space complexity measures for checking stack automata. Exactly one of three cases can occur: the complexity is either bounded by a constant, behaves (up to small technicalities explained in the paper) like a linear function, or it grows arbitrarily larger than the length of the input word. However, this result does not hold for non-erasing stack automata; we provide an example when the space complexity grows with the square root of the input length. Furthermore, an investigation is done regarding the best complexity of any machine accepting a given language, and on decidability of space complexity properties.

          Related collections

          Most cited references 10

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

          Checking automata and one-way stack languages

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

            The power of two-way deterministic checking stack automata

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

              Sets accepted by one-way stack automata are context sensitive

                Bookmark

                Author and article information

                Contributors
                jonoska@mail.usf.edu
                savchuk@usf.edu
                ibarra@cs.ucsb.edu
                jirasek.jozef@usask.ca
                mcquillan@cs.usask.ca
                prigioniero@di.unimi.it
                Journal
                978-3-030-48516-0
                10.1007/978-3-030-48516-0
                Developments in Language Theory
                Developments in Language Theory
                24th International Conference, DLT 2020, Tampa, FL, USA, May 11–15, 2020, Proceedings
                978-3-030-48515-3
                978-3-030-48516-0
                26 May 2020
                : 12086
                : 137-149
                Affiliations
                [8 ]GRID grid.170693.a, ISNI 0000 0001 2353 285X, University of South Florida, ; Tampa, FL USA
                [9 ]GRID grid.170693.a, ISNI 0000 0001 2353 285X, University of South Florida, ; Tampa, FL USA
                [10 ]GRID grid.133342.4, ISNI 0000 0004 1936 9676, Department of Computer Science, , University of California, ; Santa Barbara, CA 93106 USA
                [11 ]GRID grid.25152.31, ISNI 0000 0001 2154 235X, Department of Computer Science, , University of Saskatchewan, ; Saskatoon, SK S7N 5A9 Canada
                [12 ]GRID grid.4708.b, ISNI 0000 0004 1757 2822, Dipartimento di Informatica, , Università degli Studi di Milano, ; Milan, Italy
                Article
                11
                10.1007/978-3-030-48516-0_11
                7247887
                © Springer Nature Switzerland AG 2020

                This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.

                Categories
                Article
                Custom metadata
                © Springer Nature Switzerland AG 2020

                Comments

                Comment on this article