Výsledky vyhledávání - "Grammars and context-free languages"

Pushdown Automata and Context-Free Grammars in Bisimulation Semantics

Autor: Baeten, Jos C. M., Carissimo, Cesare, Luttik, Bas

Publikováno v: Logical Methods in Computer Science, 19(1), 15:1-15:32

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 Reac

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::79b53eb81e74c8e91989eaf1e3ecb22c
https://doi.org/10.46298/lmcs-19(1:15)2023

Zobrazit plný text záznamu

Derivative grammars: a symbolic approach to parsing with derivatives

Autor: Keshav Pingali, Ian Henriksen, Gianfranco Bilardi

Publikováno v: Proceedings of the ACM on Programming Languages. 3:1-28

We present a novel approach to context-free grammar parsing that is based on generating a sequence of grammars called derivative grammars from a given context-free grammar and input string. The generation of the derivative grammars is described by a

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::26ff9dbba3e3a5da7ef6332c531a45e2
https://doi.org/10.1145/3360553

Zobrazit plný text záznamu

Synthetic Data Generation from JSON Schemas

Autor: Cardoso, Hugo André Coelho, Ramalho, José Carlos

This document describes the steps taken in the development of DataGen From Schemas. This new version of DataGen is an application that makes it possible to automatically generate representative synthetic datasets from JSON and XML schemas, in order t

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::244e03d56ee7251506a8fad60f94163e

Zobrazit plný text záznamu

Low-Latency Sliding Window Algorithms for Formal Languages

Autor: Ganardi, Moses, Jachiet, Louis, Lohrey, Markus, Schwentick, Thomas

Low-latency sliding window algorithms for regular and context-free languages are studied, where latency refers to the worst-case time spent for a single window update or query. For every regular language $L$ it is shown that there exists a constant-l

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::12b46f61aaf0dd3a838950b9935ca1b6

Zobrazit plný text záznamu

New Analytic Techniques for Proving the Inherent Ambiguity of Context-Free Languages

Autor: Koechlin, Florent

Publikováno v: 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Foundations of Software Technology and Theoretical Computer Science (FSTTCS)
Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Dec 2022, Chennai, India. pp.10.4230/LIPIcs.FSTTCS.2022, ⟨10.4230/LIPIcs.FSTTCS.2022.41⟩

This article extends the work of Flajolet [Philippe Flajolet, 1987] on the relation between generating series and inherent ambiguity. We first propose an analytic criterion to prove the infinite inherent ambiguity of some context-free languages, and

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::dde88679a61e93d0934a1035007e7d2e

Zobrazit plný text záznamu

Adaptive synchronisation of pushdown automata

Autor: Balasubramanian, A. R., Thejaswini, K. S.

We introduce the notion of adaptive synchronisation for pushdown automata, in which there is an external observer who has no knowledge about the current state of the pushdown automaton, but can observe the contents of the stack. The observer would th

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::58b60c5724d24fa7d977ea3395efe373
http://wrap.warwick.ac.uk/158284/1/WRAP-Adaptive-synchronisation-pushdown-automata-2021.pdf

Zobrazit plný text záznamu

The expressive power of one variable used once:The chomsky hierarchy and first-order monadic constructor rewriting

Autor: Simonsen, Jakob Grue

Publikováno v: Simonsen, J G 2021, The expressive power of one variable used once : The chomsky hierarchy and first-order monadic constructor rewriting . in N Kobayashi (ed.), 6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021 ., 5, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 195, 6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021, Virtual, Buenos Aires, Argentina, 17/07/2021 . https://doi.org/10.4230/LIPIcs.FSCD.2021.5

We study the implicit computational complexity of constructor term rewriting systems where every function and constructor symbol is unary or nullary. Surprisingly, adding simple and natural constraints to rule formation yields classes of systems that

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::41ee07b7b93b2448cca146b65d5855d0
https://curis.ku.dk/ws/files/281991643/The_Expressive_Power_of_One_Variable_Used_Once.pdf

Zobrazit plný text záznamu

The Simplest Non-Regular Deterministic Context-Free Language

Autor: Jančar, Petr, Šíma, Jiří

We introduce a new notion of 𝒞-simple problems for a class 𝒞 of decision problems (i.e. languages), w.r.t. a particular reduction. A problem is 𝒞-simple if it can be reduced to each problem in 𝒞. This can be viewed as a conceptual counter

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::81127b9829b5921259f67498a70fde13

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání