Document Open Access Logo

Pushdown Automata and Context-Free Grammars in Bisimulation Semantics

Authors Jos C. M. Baeten , Cesare Carissimo, Bas Luttik

PDF
Thumbnail PDF

File

LIPIcs.CALCO.2021.8.pdf
  • Filesize: 0.69 MB
  • 16 pages

Document Identifiers

Author Details

Jos C. M. Baeten
  • CWI, Amsterdam, The Netherlands
  • University of Amsterdam, The Netherlands
Cesare Carissimo
  • University of Amsterdam, The Netherlands
Bas Luttik
  • Eindhoven University of Technology, The Netherlands

Cite AsGet BibTex

Jos C. M. Baeten, Cesare Carissimo, and Bas Luttik. Pushdown Automata and Context-Free Grammars in Bisimulation Semantics. In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CALCO.2021.8

Abstract

The Turing machine models an old-fashioned computer, that does not interact with the user or with other computers, and only does batch processing. Therefore, we came up with a Reactive Turing Machine that does not have these shortcomings. In the Reactive Turing Machine, transitions have labels to give a notion of interactivity. In the resulting process graph, we use bisimilarity instead of language equivalence. Subsequently, we considered other classical theorems and notions from automata theory and formal languages theory. In this paper, we consider the classical theorem of the correspondence between pushdown automata and context-free grammars. By changing the process operator of sequential composition to a sequencing operator with intermediate acceptance, we get a better correspondence in our setting. We find that the missing ingredient to recover the full correspondence is the addition of a notion of state awareness.

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive computation
  • Theory of computation → Turing machines
  • Theory of computation → Grammars and context-free languages
  • Theory of computation → Process calculi
Keywords
  • pushdown automaton
  • context-free grammar
  • bisimilarity
  • intermediate acceptance
  • state awareness

Metrics

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

References

  1. J. C. M. Baeten and J. A. Bergstra. Process algebra with propositional signals. Theor. Comput. Sci., 177(2):381-405, 1997. URL: https://doi.org/10.1016/S0304-3975(96)00253-8.
  2. J. C. M. Baeten, P. J. L. Cuijpers, B. Luttik, and P. J. A. van Tilburg. A process-theoretic look at automata. In F. Arbab and M. Sirjani, editors, Fundamentals of Software Engineering, Third IPM International Conference, FSEN 2009, Kish Island, Iran, April 15-17, 2009, Revised Selected Papers, volume 5961 of Lecture Notes in Computer Science, pages 1-33. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-11623-0_1.
  3. J. C. M. Baeten, P. J. L. Cuijpers, and P. J. A. van Tilburg. A context-free process as a pushdown automaton. In F. van Breugel and M. Chechik, editors, Proceedings CONCUR'08, number 5201 in Lecture Notes in Computer Science, pages 98-113, 2008. Google Scholar
  4. J. C. M. Baeten, B. Luttik, and P. J. A. van Tilburg. Reactive Turing machines. Information and Computation, 231:143-166, 2013. Fundamentals of Computation Theory. URL: https://doi.org/10.1016/j.ic.2013.08.010.
  5. J. C. M. Baeten, B. Luttik, and F. Yang. Sequential composition in the presence of intermediate termination (extended abstract). In K. Peters and S. Tini, editors, Proceedings Combined 24th International Workshop on Expressiveness in Concurrency and 14th Workshop on Structural Operational Semantics and 14th Workshop on Structural Operational Semantics, EXPRESS/SOS 2017, Berlin, Germany, 4th September 2017., volume 255 of EPTCS, pages 1-17, 2017. URL: https://doi.org/10.4204/EPTCS.255.1.
  6. J. C.M. Baeten, A. A. Basten, and M. A. Reniers. Process algebra: equational theories of communicating processes, volume 50. Cambridge university press, 2010. Google Scholar
  7. A. Belder. Decidability of bisimilarity and axiomatisation for sequential processes in the presence of intermediate termination. Master’s thesis, Eindhoven University of Technology, 2018. Available from URL: https://research.tue.nl/en/studentTheses/decidability-of-bisimilarity-and-axiomatisation-for-sequential-pr.
  8. A. Belder, B. Luttik, and J. C. M. Baeten. Sequencing and intermediate acceptance: axiomatisation and decidability of bisimilarity. In Markus Roggenbach and Ana Sokolova, editors, 8th Conference on Algebra and Coalgebra in Computer Science, CALCO 2019, Leibniz International Proceedings in Informatics, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.CALCO.2019.11.
  9. R. N. Bol and J. F. Groote. The meaning of negative premises in transition system specifications. J. ACM, 43(5):863-914, 1996. URL: https://doi.org/10.1145/234752.234756.
  10. D. Goldin and P. Wegner. The interactive nature of computing: Refuting the strong Church-Turing thesis. Minds and Machines, 18(1):17-38, 2008. Google Scholar
  11. J. F. Groote. Transition system specifications with negative premises. Theor. Comput. Sci., 118(2):263-299, 1993. URL: https://doi.org/10.1016/0304-3975(93)90111-6.
  12. B. Luttik. Divergence-preserving branching bisimilarity. In O. Dardha and J. Rot, editors, Proceedings Combined 27th International Workshop on Expressiveness in Concurrency and 17th Workshop on Structural Operational Semantics, EXPRESS/SOS 2020, and 17th Workshop on Structural Operational Semantics, Online, 31 August 2020, volume 322 of EPTCS, pages 3-11, 2020. URL: https://doi.org/10.4204/EPTCS.322.2.
  13. R. J. van Glabbeek. The meaning of negative premises in transition system specifications II. J. Log. Algebr. Program., 60-61:229-258, 2004. URL: https://doi.org/10.1016/j.jlap.2004.03.007.
  14. R. J. van Glabbeek and W. P. Weijland. Branching time and abstraction in bisimulation semantics. Journal of the ACM, 43(3):555-600, 1996. URL: https://doi.org/10.1145/233551.233556.
  15. C. Verhoef. A congruence theorem for structured operational semantics with predicates and negative premises. Nord. J. Comput., 2(2):274-302, 1995. Google Scholar
  16. P. Wegner. Why interaction is more powerful than algorithms. Communications of the ACM, 40(5):80-91, 1997. 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 Imprint Privacy Contact