Zobrazeno 1 - 10
of 17
pro vyhledávání: '"• Theory of computation → Grammars and context-free languages"'
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
https://doi.org/10.46298/lmcs-19(1:15)2023
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
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
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⟩
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
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
http://wrap.warwick.ac.uk/158284/1/WRAP-Adaptive-synchronisation-pushdown-automata-2021.pdf
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
https://doi.org/10.1145/3360553
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
https://curis.ku.dk/ws/files/281991643/The_Expressive_Power_of_One_Variable_Used_Once.pdf
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
Autor:
Ambridge, Ben
Many modern NLP models are already close to simulating children’s language acquisition; the main thing they currently lack is a "real world" representation of semantics that allows them to map from form to meaning and vice-versa. The aim of this "C
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5077355ba60abb02b51c70f9dc327cba
https://doi.org/10.4230/oasics.ldk.2021.4
https://doi.org/10.4230/oasics.ldk.2021.4
Autor:
Clokie, Trevor, Lidbetter, Thomas F., Molina Lovett, Antonio J., Shallit, Jeffrey, Witzman, Leon
Following Stolarsky, we say that a natural number n is flimsy in base b if some positive multiple of n has smaller digit sum in base b than n does; otherwise it is sturdy . We develop algorithmic methods for the study of sturdy and flimsy numbers. We
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6d8c26fdd1b4478a4a15b51180453ab0