On Emptiness and Membership Problems for Set Automata | SpringerLink
Skip to main content
Springer Nature Link
Log in

On Emptiness and Membership Problems for Set Automata

  • Conference paper
  • First Online:
Computer Science – Theory and Applications (CSR 2018)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10846))

Included in the following conference series:

  • 1101 Accesses

Abstract

We consider a computational model which is known as set automata.

The set automata are one-way finite automata with an additional storage—the set. There are two kinds of set automata—the deterministic and the nondeterministic ones. We denote them as DSA and NSA respectively. The model was introduced by Kutrib et al. in 2014 in [2, 3].

In this paper we characterize algorithmic complexity of the emptiness and membership problems for set automata. More definitely, we prove that both problems are \({\mathbf {PSPACE}}\)-complete for both kinds of set automata.

The study has been funded by the Russian Academic Excellence Project ‘5-100’. Supported in part by RFBR grants 16–01–00362 and 17–51-10005.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    The structural Propositions 8 and 9 hold for all query languages. Lemma 10 and the \({\mathbf {PSPACE}}\) algorithm below are applied to regular query languages only.

References

  1. Kozen, D.: Lower bounds for natural proof systems. In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, SFCS 1977, pp. 254–266. IEEE Computer Society, Washington, D.C. (1977)

    Google Scholar 

  2. Kutrib, M., Malcher, A., Wendlandt, M.: Deterministic set automata. In: Shur, A.M., Volkov, M.V. (eds.) DLT 2014. LNCS, vol. 8633, pp. 303–314. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-09698-8_27

    Chapter  Google Scholar 

  3. Kutrib, M., Malcher, A., Wendlandt, M.: Regularity and size of set automata. In: Jürgensen, H., Karhumäki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 282–293. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-09704-6_25

    Chapter  MATH  Google Scholar 

  4. Kutrib, M., Malcher, A., Wendlandt, M.: Set automata. Int. J. Found. Comput. Sci. 27(02), 187–214 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  5. Lange, K.-J., Rossmanith, P.: The emptiness problem for intersections of regular languages. In: Havel, I.M., Koubek, V. (eds.) MFCS 1992. LNCS, vol. 629, pp. 346–354. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-55808-X_33

    Chapter  Google Scholar 

  6. Lange, K.-J., Reinhardt, K.: Set automata. In: Bridges, D.S., Calude, C., Gibbons, J., Reeves, S., Witten, L. (eds.) Combinatorics, Complexity, Logic. Proceedings of the DMTCS 1996, pp. 321–329. Springer, Heidelberg (1996)

    Google Scholar 

  7. Rubtsov, A.A., Vyalyi, M.N.: On computational complexity of set automata. In: Charlier, É., Leroy, J., Rigo, M. (eds.) DLT 2017. LNCS, vol. 10396, pp. 332–344. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-62809-7_25

    Chapter  Google Scholar 

Download references

Acknowledgments

The authors are thankful to the first referee for helpful comments.

Author information

Authors and Affiliations

  1. National Research University Higher School of Economics, Moscow, Russia

    A. Rubtsov & M. Vyalyi

  2. Moscow Institute of Physics and Technology, Moscow, Russia

    A. Rubtsov & M. Vyalyi

  3. Dorodnicyn Computing Centre, FRC CSC RAS, Moscow, Russia

    M. Vyalyi

Authors
  1. A. Rubtsov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. Vyalyi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. Vyalyi .

Editor information

Editors and Affiliations

  1. Department of Informatics, University of Bergen, Bergen, Norway

    Fedor V. Fomin

  2. Steklov Mathematical Institute, Moscow, Russia

    Vladimir V. Podolskii

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer International Publishing AG, part of Springer Nature

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Rubtsov, A., Vyalyi, M. (2018). On Emptiness and Membership Problems for Set Automata. In: Fomin, F., Podolskii, V. (eds) Computer Science – Theory and Applications. CSR 2018. Lecture Notes in Computer Science(), vol 10846. Springer, Cham. https://doi.org/10.1007/978-3-319-90530-3_25

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-90530-3_25

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-90529-7

  • Online ISBN: 978-3-319-90530-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation