{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T03:17:45Z","timestamp":1773717465482,"version":"3.50.1"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2023,3,2]],"date-time":"2023-03-02T00:00:00Z","timestamp":1677715200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>The Turing machine models an old-fashioned computer, that does not interact\nwith the user or with other computers, and only does batch processing.\nTherefore, we came up with a Reactive Turing Machine that does not have these\nshortcomings. In the Reactive Turing Machine, transitions have labels to give a\nnotion of interactivity. In the resulting process graph, we use bisimilarity\ninstead of language equivalence.\n  Subsequently, we considered other classical theorems and notions from\nautomata theory and formal languages theory. In this paper, we consider the\nclassical theorem of the correspondence between pushdown automata and\ncontext-free grammars. By changing the process operator of sequential\ncomposition to a sequencing operator with intermediate acceptance, we get a\nbetter correspondence in our setting. We find that the missing ingredient to\nrecover the full correspondence is the addition of a notion of state awareness.<\/jats:p>","DOI":"10.46298\/lmcs-19(1:15)2023","type":"journal-article","created":{"date-parts":[[2023,3,2]],"date-time":"2023-03-02T11:35:16Z","timestamp":1677756916000},"source":"Crossref","is-referenced-by-count":4,"title":["Pushdown Automata and Context-Free Grammars in Bisimulation Semantics"],"prefix":"10.46298","volume":"Volume 19, Issue 1","author":[{"given":"Jos C. M.","family":"Baeten","sequence":"first","affiliation":[]},{"given":"Cesare","family":"Carissimo","sequence":"additional","affiliation":[]},{"given":"Bas","family":"Luttik","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2023,3,2]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/11014\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/11014\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:20:44Z","timestamp":1687292444000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/9178"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,2]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-19(1:15)2023","relation":{"has-preprint":[{"id-type":"arxiv","id":"2203.01713v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2203.01713v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2203.01713","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2203.01713","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,2]]},"article-number":"9178"}}