Zobrazeno 1 - 10
of 213
pro vyhledávání: '"Grandjean, Etienne"'
Autor:
Grandjean, Étienne, Jachiet, Louis
In the literature of algorithms, the specific computation model is often not explicit as it is assumed that the model of computation is the RAM (Random Access Machine) model. However, the RAM model itself is ill-founded in the literature, with dispar
Externí odkaz:
http://arxiv.org/abs/2206.13851
Publikováno v:
In Theoretical Computer Science 1 March 2024 987
Autor:
Grandjean, Étienne, Grente, Théo
Descriptive complexity may be useful to design programs in a natural declarative way. This is important for parallel computation models such as cellular automata, because designing parallel programs is considered difficult. Our paper establishes logi
Externí odkaz:
http://arxiv.org/abs/1902.05720
This paper deals with descriptive complexity of picture languages of any dimension by syntactical fragments of existential second-order logic. - We uniformly generalize to any dimension the characterization by Giammarresi et al. \cite{GRST96} of the
Externí odkaz:
http://arxiv.org/abs/1201.5853
Proving lower bounds remains the most difficult of tasks in computational complexity theory. In this paper, we show that whereas most natural NP-complete problems belong to NLIN (linear time on nondeterministic RAMs), some of them, typically the plan
Externí odkaz:
http://arxiv.org/abs/cs/0606058
Autor:
Durand, Arnaud, Grandjean, Etienne
In this paper, we consider first-order logic over unary functions and study the complexity of the evaluation problem for conjunctive queries described by such kind of formulas. A natural notion of query acyclicity for this language is introduced and
Externí odkaz:
http://arxiv.org/abs/cs/0605008
Autor:
Durand, Arnaud, Grandjean, Etienne
A bounded degree structure is either a relational structure all of whose relations are of bounded degree or a functional structure involving bijective functions only. In this paper, we revisit the complexity of the evaluation problem of not necessari
Externí odkaz:
http://arxiv.org/abs/cs/0507020
Autor:
Grente, Théo, Grandjean, Etienne
The expressive power of the class Conj of conjunctive languages, i.e. languages generated by the conjunctive grammars of Okhotin, is largely unknown, while its restriction LinConj to linear conjunctive grammars equals the class of languages recognize
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::792cd8dde4f972b9b0e2ff63076de5d3
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.