SpringerLink
Log in

Decision Problems for Restricted Variants of Two-Dimensional Automata

  • Conference paper
  • First Online:
Implementation and Application of Automata (CIAA 2019)

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

Included in the following conference series:

  • 369 Accesses

Abstract

A two-dimensional finite automaton has a read-only input head that moves in four directions on a finite array of cells labelled by symbols of the input alphabet. A three-way two-dimensional automaton is prohibited from making upward moves, while a two-way two-dimensional automaton can only move downward and rightward.

We show that the language emptiness problem for unary three-way nondeterministic two-dimensional automata is -complete, and is in for general-alphabet two-way nondeterministic two-dimensional automata. We show that the language equivalence problem for two-way deterministic two-dimensional automata is decidable. This is the first known positive decidability result for the equivalence problem on two-dimensional automata over a general alphabet. We show that there exists a unary three-way deterministic two-dimensional automaton with a nonregular column projection, and we show that the row projection of a unary three-way nondeterministic two-dimensional automaton is always regular.

Smith and Salomaa were supported by Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.

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
EUR 32.99 /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
USD 29.95
Price excludes VAT (Canada)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (Canada)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (Canada)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Anselmo, M., Giammarresi, D., Madonia, M.: New operations and regular expressions for two-dimensional languages over one-letter alphabet. Theor. Comput. Sci. 340(2), 408–431 (2005). https://doi.org/10.1016/j.tcs.2005.03.031

    Article  MathSciNet  MATH  Google Scholar 

  2. Blum, M., Hewitt, C.: Automata on a 2-dimensional tape. In: Miller, R.E. (ed.) SWAT 1967, pp. 155–160 (1967). https://doi.org/10.1109/FOCS.1967.6

  3. Dong, J., **, W.: Comparison of two-way two-dimensional finite automata and three-way two-dimensional finite automata. In: Yang, X. (ed.) CSSS 2012, pp. 1904–1906 (2012). https://doi.org/10.1109/CSSS.2012.474

  4. Galil, Z.: Hierarchies of complete problems. Acta Inf. 6(1), 77–88 (1976). https://doi.org/10.1007/BF00263744

    Article  MathSciNet  MATH  Google Scholar 

  5. Greibach, S.: Checking automata and one-way stack languages. J. Comput. Syst. Sci. 3(2), 196–217 (1969). https://doi.org/10.1016/S0022-0000(69)80012-7

    Article  MathSciNet  MATH  Google Scholar 

  6. Hunt III, H.B.: On the time and tape complexity of languages I. In: Aho, A.V. (ed.) STOC 1973, pp. 10–19 (1973). https://doi.org/10.1145/800125.804030

  7. Ibarra, O.H., Dang, Z., Li, Q.: Accepting runs in a two-way finite automation. Inf. Comput. 260, 1–8 (2018). https://doi.org/10.1016/j.ic.2018.03.002

    Article  MATH  Google Scholar 

  8. Inoue, K., Takanami, I.: A note on decision problems for three-way two-dimensional finite automata. Inf. Process. Lett. 10(4–5), 245–248 (1980). https://doi.org/10.1016/0020-0190(80)90151-9

    Article  MathSciNet  MATH  Google Scholar 

  9. Inoue, K., Takanami, I.: A survey of two-dimensional automata theory. Inf. Sci. 55(1–3), 99–121 (1991). https://doi.org/10.1016/0020-0255(91)90008-I

    Article  MathSciNet  MATH  Google Scholar 

  10. Kari, J., Moore, C.: Rectangles and squares recognized by two-dimensional automata. In: Karhumäki, J., Maurer, H., Păun, G., Rozenberg, G. (eds.) Theory Is Forever. LNCS, vol. 3113, pp. 134–144. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27812-2_13

    Chapter  Google Scholar 

  11. Kari, J., Salo, V.: A survey on picture-walking automata. In: Kuich, W., Rahonis, G. (eds.) Algebraic Foundations in Computer Science. LNCS, vol. 7020, pp. 183–213. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24897-9_9

    Chapter  Google Scholar 

  12. Kinber, E.B.: Three-way automata on rectangular tapes over a one-letter alphabet. Inform. Sci. 35, 61–77 (1985). https://doi.org/10.1016/0020-0255(85)90041_6

    Article  MathSciNet  MATH  Google Scholar 

  13. Petersen, H.: Some results concerning two-dimensional Turing machines and finite automata. In: Reichel, H. (ed.) FCT 1995. LNCS, vol. 965, pp. 374–382. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60249-6_69

    Chapter  Google Scholar 

  14. Pighizzini, G.: Two-way finite automata: old and recent results. Fund. Inf. 126(2–3), 225–246 (2013). https://doi.org/10.3233/FI-2013-879

    Article  MathSciNet  MATH  Google Scholar 

  15. Rosenfeld, A.: Picture Languages: Formal Models for Picture Recognition. Computer Science and Applied Mathematics. Academic Press, New York (1979)

    MATH  Google Scholar 

  16. Smith, T.J.: Two-dimensional automata. Technical report 2019–637, Queen’s University, Kingston (2019)

    Google Scholar 

  17. Taniguchi, K., Kasami, T.: Some decision problems for two-dimensional nonwriting automata. Trans. Inst. Electron. Comm. Engrs. Jpn. 54–C(7), 578–585 (1971)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computing, Queen’s University, Kingston, ON, K7L 2N8, Canada

    Taylor J. Smith & Kai Salomaa

Authors
  1. Taylor J. Smith
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kai Salomaa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Taylor J. Smith or Kai Salomaa .

Editor information

Editors and Affiliations

  1. Slovak Academy of Sciences, Košice, Slovakia

    Michal Hospodár

  2. Slovak Academy of Sciences, Košice, Slovakia

    Galina Jirásková

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Smith, T.J., Salomaa, K. (2019). Decision Problems for Restricted Variants of Two-Dimensional Automata. In: Hospodár, M., Jirásková, G. (eds) Implementation and Application of Automata. CIAA 2019. Lecture Notes in Computer Science(), vol 11601. Springer, Cham. https://doi.org/10.1007/978-3-030-23679-3_18

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-23679-3_18

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-23678-6

  • Online ISBN: 978-3-030-23679-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation