Document Open Access Logo

Regular Languages: To Finite Automata and Beyond (Invited Talk)

Author Luca Prigioniero

PDF
Thumbnail PDF

File

OASIcs.AUTOMATA.2021.2.pdf
  • Filesize: 0.66 MB
  • 16 pages

Document Identifiers

Author Details

Luca Prigioniero
  • Dipartimento di Informatica, Università degli Studi di Milano, Milan, Italy

Acknowledgements

This paper and the research behind it would not have been possible without the support and the valuable comments of Giovanni Pighizzini.

Cite As Get BibTex

Luca Prigioniero. Regular Languages: To Finite Automata and Beyond (Invited Talk). In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/OASIcs.AUTOMATA.2021.2

Abstract

It is well known that the class of regular languages coincides with the class of languages recognized by finite automata. Nevertheless, many other characterizations of this class in terms of computational devices and generative models are present in the literature. For example, by suitably restricting more powerful models such as context-free grammars, pushdown automata, and Turing machines, it is possible to obtain formal models that generate or recognize regular languages only. These restricted formalisms provide alternative representations of regular languages that may be significantly more concise than other models that share the same expressive power.
The goal of this work is to provide an overview of old and recent results on these formal systems from a descriptional complexity perspective, that is by considering the relationships between the sizes of such devices. We also present some results related to the investigation of the famous question posed by Sakoda and Sipser in 1978, concerning the size blowups from nondeterministic finite automata to two-way deterministic finite automata.

Subject Classification

ACM Subject Classification
  • Theory of computation → Regular languages
  • Theory of computation → Models of computation
Keywords
  • Regular languages
  • descriptional complexity
  • finite automata

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Maris Alberts. Space complexity of alternating Turing machines. In Fundamentals of Computation Theory (FCT) '85, volume 199 of Lecture Notes in Computer Science, pages 1-7. Springer, 1985. URL: https://doi.org/10.1007/BFb0028785.
  2. Marcella Anselmo, Dora Giammarresi, and Stefano Varricchio. Finite automata and non-self-embedding grammars. In Conference on Implementation and Application of Automata (CIAA) 2002, volume 2608 of Lecture Notes in Computer Science, pages 47-56. Springer, 2002. URL: https://doi.org/10.1007/3-540-44977-9_4.
  3. Zuzana Bednárová, Viliam Geffert, Carlo Mereghetti, and Beatrice Palano. Removing nondeterminism in constant height pushdown automata. Information and Computation, 237:257-267, 2014. URL: https://doi.org/10.1016/j.ic.2014.03.002.
  4. Zuzana Bednárová, Viliam Geffert, Klaus Reinhardt, and Abuzer Yakaryilmaz. New results on the minimum amount of useful space. International Journal of Foundations of Computer Science, 27(2):259-282, 2016. URL: https://doi.org/10.1142/S0129054116400098.
  5. Piotr Berman and Andrzej Lingas. On the complexity of regular languages in terms of finite automata. Technical Report 304, Polish Academy of Sciences, 1977. Google Scholar
  6. Noam Chomsky. A note on phrase structure grammars. Information and Control, 2(4):393-395, 1959. URL: https://doi.org/10.1016/S0019-9958(59)80017-6.
  7. Noam Chomsky. On certain formal properties of grammars. Information and Control, 2(2):137-167, 1959. URL: https://doi.org/10.1016/S0019-9958(59)90362-6.
  8. Noam Chomsky. Context-Free Grammars and Pushdown Storage. Technical Report 65, Massachusetts Institute of Technology, Research Laboratory of Electronics, 1962. URL: https://dspace.mit.edu/bitstream/handle/1721.1/53697/RLE_QPR_065_XVII.pdf.
  9. David Gajser. Verifying time complexity of Turing machines. Theoretical Computer Science, 600:86-97, 2015. URL: https://doi.org/10.1016/j.tcs.2015.07.028.
  10. Viliam Geffert, Bruno Guillon, and Giovanni Pighizzini. Two-way automata making choices only at the endmarkers. Information and Computation, 239:71-86, 2014. URL: https://doi.org/10.1016/j.ic.2014.08.009.
  11. Viliam Geffert, Carlo Mereghetti, and Beatrice Palano. More concise representation of regular languages by automata and regular expressions. Information and Computation, 208(4):385-394, 2010. URL: https://doi.org/10.1016/j.ic.2010.01.002.
  12. Viliam Geffert, Carlo Mereghetti, and Giovanni Pighizzini. Converting two-way nondeterministic unary automata into simpler automata. Theoretical Computer Science, 295(1–3):189-203, 2003. URL: https://doi.org/10.1016/S0304-3975(02)00403-6.
  13. Viliam Geffert and Giovanni Pighizzini. Two-way unary automata versus logarithmic space. Information and Computation, 209(7):1016-1025, 2011. URL: https://doi.org/10.1016/j.ic.2011.03.003.
  14. Jonathan Goldstine, Martin Kappes, Chandra M. R. Kintala, Hing Leung, Andreas Malcher, and Detlef Wotschke. Descriptional complexity of machines with limited resources. Journal of Universal Computer Science, 8(2):193-234, 2002. URL: https://doi.org/10.3217/jucs-008-02-0193.
  15. Bruno Guillon, Giovanni Pighizzini, and Luca Prigioniero. Non-self-embedding grammars, constant-height pushdown automata, and limited automata. International Journal of Foundations of Computer Science, 31(8):1133-1157, 2020. URL: https://doi.org/10.1142/S0129054120420071.
  16. Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero, and Daniel Průša. Two-way automata and one-tape machines - read only versus linear time. In Developments in Language Theory (DLT) 2018, volume 11088 of Lecture Notes in Computer Science, pages 366-378. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-98654-8_30.
  17. Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero, and Daniel Průša. Converting nondeterministic two-way automata into small deterministic linear-time machines. CoRR, abs/2103.05485, 2021. URL: http://arxiv.org/abs/2103.05485.
  18. Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero, and Daniel Průša. Weight-reducing Turing machines. CoRR, abs/2103.05486, 2021. URL: http://arxiv.org/abs/2103.05486.
  19. Bruno Guillon and Luca Prigioniero. Linear-time limited automata. Theoretical Computer Science, 798:95-108, 2019. URL: https://doi.org/10.1016/j.tcs.2019.03.037.
  20. Yo-Sub Han, Arto Salomaa, and Kai Salomaa. Ambiguity, nondeterminism and state complexity of finite automata. Acta Cybernetica, 23(1):141-157, 2017. URL: https://doi.org/10.14232/actacyb.23.1.2017.9.
  21. Juris Hartmanis. Context-free languages and Turing machine computations. In Mathematical Aspects of Computer Science, volume 19 of Proceedings of Symposia in Applied Mathematics, pages 42-51. American Mathematical Society, 1967. Google Scholar
  22. Fred C. Hennie. One-tape, off-line Turing machine computations. Information and Control, 8(6):553-578, 1965. URL: https://doi.org/10.1016/S0019-9958(65)90399-2.
  23. Thomas N. Hibbard. A generalization of context-free determinism. Information and Control, 11(1/2):196-238, 1967. URL: https://doi.org/10.1016/S0019-9958(67)90513-X.
  24. Markus Holzer and Martin Kutrib. Descriptional complexity - an introductory survey. In Scientific Applications of Language Methods, pages 1-58. Imperial College Press, 2010. URL: https://doi.org/10.1142/9781848165458_0001.
  25. Markus Holzer and Martin Kutrib. One-time nondeterministic computations. International Journal of Foundations of Computer Science, 30(6-7):1069-1089, 2019. URL: https://doi.org/10.1142/S012905411940029X.
  26. John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979. Google Scholar
  27. Juraj Hromkovič and Georg Schnitger. Nondeterminism versus determinism for two-way finite automata: Generalizations of Sipser’s separation. In International Colloquium on Automata, Languages, and Programming (ICALP) 2003, volume 2719 of Lecture Notes in Computer Science, pages 439-451. Springer, 2003. URL: https://doi.org/10.1007/3-540-45061-0_36.
  28. Christos A. Kapoutsis. Nondeterminism is essential in small two-way finite automata with few reversals. Information and Computation, 222:208-227, 2013. URL: https://doi.org/10.1016/j.ic.2012.11.001.
  29. Christos A. Kapoutsis. Two-way automata versus logarithmic space. Theory of Computing Systems, 55(2):421-447, 2014. URL: https://doi.org/10.1007/s00224-013-9465-0.
  30. Christos A. Kapoutsis and Giovanni Pighizzini. Two-way automata characterizations of L/poly versus NL. Theory of Computing Systems, 56(4):662-685, 2015. URL: https://doi.org/10.1007/s00224-014-9560-x.
  31. Chris Keeler and Kai Salomaa. Nondeterminism growth and state complexity. In Descriptional Complexity of Formal Systems (DCFS) 2019, volume 11612 of Lecture Notes in Computer Science, pages 210-222. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-23247-4_16.
  32. Alica Kelemenová. Complexity of normal form grammars. Theoretical Computer Science, 28:299-314, 1984. URL: https://doi.org/10.1016/0304-3975(83)90026-9.
  33. Sige-Yuki Kuroda. Classes of languages and linear-bounded automata. Information and Control, 7(2):207-223, 1964. URL: https://doi.org/10.1016/S0019-9958(64)90120-2.
  34. Martin Kutrib, Giovanni Pighizzini, and Matthias Wendlandt. Descriptional complexity of limited automata. Information and Computation, 259(2):259-276, 2018. URL: https://doi.org/10.1016/j.ic.2017.09.005.
  35. Hing Leung. Descriptional complexity of nfa of different ambiguity. International Journal of Foundations of Computer Science, 16(5):975-984, 2005. URL: https://doi.org/10.1142/S0129054105003418.
  36. Carlo Mereghetti and Giovanni Pighizzini. Two-way automata simulations and unary languages. Journal of Automata, Languages and Combinatorics, 5(3):287-300, 2000. URL: https://doi.org/10.25596/jalc-2000-287.
  37. Albert R. Meyer and Michael J. Fischer. Economy of description by automata, grammars, and formal systems. In Switching Automata Theory (SwAT) 1971, pages 188-191. IEEE Computer Society, 1971. URL: https://doi.org/10.1109/SWAT.1971.11.
  38. Alexander Okhotin. Non-erasing variants of the Chomsky-Schützenberger theorem. In Developments in Language Theory (DLT) 2012, volume 7410 of Lecture Notes in Computer Science, pages 121-129. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-31653-1_12.
  39. Giovanni Pighizzini. Nondeterministic one-tape off-line Turing machines. Journal of Automata, Languages and Combinatorics, 14(1):107-124, 2009. URL: https://doi.org/10.25596/jalc-2009-107.
  40. Giovanni Pighizzini. Two-way finite automata: Old and recent results. Fundamenta Informaticae, 126(2-3):225-246, 2013. URL: https://doi.org/10.3233/FI-2013-879.
  41. Giovanni Pighizzini. Limited automata: Properties, complexity and variants. In Descriptional Complexity of Formal Systems (DCFS) 2019, volume 11612 of Lecture Notes in Computer Science, pages 57-73. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-23247-4_4.
  42. Giovanni Pighizzini and Andrea Pisoni. Limited automata and regular languages. International Journal of Foundations of Computer Science, 25(7):897-916, 2014. URL: https://doi.org/10.1142/S0129054114400140.
  43. Giovanni Pighizzini and Andrea Pisoni. Limited automata and context-free languages. Fundamenta Informaticae, 136(1-2):157-176, 2015. URL: https://doi.org/10.3233/FI-2015-1148.
  44. Giovanni Pighizzini and Luca Prigioniero. Limited automata and unary languages. Information and Computation, 266:60-74, 2019. URL: https://doi.org/10.1016/j.ic.2019.01.002.
  45. Giovanni Pighizzini and Luca Prigioniero. Pushdown automata and constant height: Decidability and bounds. In Descriptional Complexity of Formal Systems (DCFS) 2019, volume 11612 of Lecture Notes in Computer Science, pages 260-271. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-23247-4_20.
  46. Giovanni Pighizzini and Luca Prigioniero. Non-self-embedding grammars and descriptional complexity. Fundamenta Informaticae, 180(1-2):103-122, 2021. To appear. URL: https://doi.org/10.3233/FI-2021-2036.
  47. Giovanni Pighizzini, Jeffrey O. Shallit, and Ming-wei Wang. Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds. Journal of Computer and System Sciences, 65(2):393-414, 2002. URL: https://doi.org/10.1006/jcss.2002.1855.
  48. Luca Prigioniero. Regular Languages: To Finite Automata and Beyond - Succinct Descriptions and Optimal Simulations. PhD thesis, Università degli Studi di Milano, Dipartimento di Informatica, 2020. URL: https://doi.org/10.13130/prigioniero-luca_phd2020-01-31.
  49. Luca Prigioniero. Regular languages: To finite automata and beyond succinct descriptions and optimal simulations. Bulletin of EATCS, 131, 2020. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/619.
  50. Daniel Průša. Weight-reducing Hennie machines and their descriptional complexity. In Language and Automata Theory and Applications (LATA) 2014, volume 8370 of Lecture Notes in Computer Science, pages 553-564, 2014. URL: https://doi.org/10.1007/978-3-319-04921-2_45.
  51. Michael O. Rabin and Dana Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3(2):pp. 114-125, 1959. URL: https://doi.org/10.1147/rd.32.0114.
  52. William J. Sakoda and Michael Sipser. Nondeterminism and the size of two way finite automata. In Symposium on Theory of Computing (SToC) 1978, pages 275-286. ACM, 1978. URL: https://doi.org/10.1145/800133.804357.
  53. John C. Shepherdson. The reduction of two-way automata to one-way automata. IBM Journal of Research and Development, 3(2):198-200, 1959. URL: https://doi.org/10.1147/rd.32.0198.
  54. Michael Sipser. Halting space-bounded computations. Theoretical Computer Science, 10(3):335-338, 1980. URL: https://doi.org/10.1016/0304-3975(80)90053-5.
  55. Kohtaro Tadaki, Tomoyuki Yamakami, and Jack C. H. Lin. Theory of one-tape linear-time Turing machines. Theoretical Computer Science, 411(1):22-43, 2010. URL: https://doi.org/10.1016/j.tcs.2009.08.031.
  56. Klaus W. Wagner and Gerd Wechsung. Computational Complexity. D. Reidel Publishing Company, Dordrecht, 1986. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact