DROPS

Document

DOI: 10.4230/LIPIcs.CALCO.2021.8

Pushdown Automata and Context-Free Grammars in Bisimulation Semantics

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

Published in: LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{baeten_et_al:LIPIcs.CALCO.2021.8,
  author =	{Baeten, Jos C. M. and Carissimo, Cesare and Luttik, Bas},
  title =	{{Pushdown Automata and Context-Free Grammars in Bisimulation Semantics}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.8},
  URN =		{urn:nbn:de:0030-drops-153632},
  doi =		{10.4230/LIPIcs.CALCO.2021.8},
  annote =	{Keywords: pushdown automaton, context-free grammar, bisimilarity, intermediate acceptance, state awareness}
}

Search Results

Documents authored by Carissimo, Cesare

Pushdown Automata and Context-Free Grammars in Bisimulation Semantics

Abstract

Cite as

Thanks for your feedback!

Could not send message