Theoretical Computer Science: Computability, Decidability and Logic

Autor: Jean-Yves Marion, Rémi Gilleron, Gilles Dowek, Serge Grigorieff, Simon Perdrix, Olivier Bournez, Sophie Tison

Publikováno v: A Guided Tour of Artificial Intelligence Research ISBN: 9783030061692
A Guided Tour of Artificial Intelligence Research-Volume III: Interfaces and Applications of Artificial Intelligence (10.1007/978-3-030-06170-8)
A Guided Tour of Artificial Intelligence Research-Volume III: Interfaces and Applications of Artificial Intelligence (10.1007/978-3-030-06170-8), Springer International Publishing, pp.1-50, 2020, ⟨10.1007/978-3-030-06170-8_1⟩

International audience; This chapter deals with a question in the very core of IA: what can be computed by a machine? An agreement has been reached on the answer brought by Alan Turing in 1936. Indeed, all other proposed approaches have led to exactl

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::714369ba9254ad8cb7b4b6e981c4955a
https://doi.org/10.1007/978-3-030-06170-8_1

Oblivious and Semi-Oblivious Boundedness for Existential Rules

Autor: Sophie Tison, Marie-Laure Mugnier, Lily Gallois, Michel Leclère, Federico Ulliana, Pierre Bourhis

Publikováno v: IJCAI 2019-28th International Joint Conference on Artificial Intelligence
IJCAI 2019-28th International Joint Conference on Artificial Intelligence, Aug 2019, Macao, China. pp.1581-1587, ⟨10.24963/ijcai.2019/219⟩
IJCAI
HAL
[Research Report] LIRMM (UM, CNRS). 2020
28th nternational Joint Conference on Artificial Intelligence
IJCAI 2019-International Joint Conference on Artificial Intelligence
IJCAI 2019-International Joint Conference on Artificial Intelligence, Aug 2019, Macao, China

We study the notion of boundedness in the context of positive existential rules, that is, whether there exists an upper bound to the depth of the chase procedure , that is independent from the initial instance. By focussing our attention on the obliv

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::81b5688c7aefabe3e3a33e5416847a5d
https://hal-lirmm.ccsd.cnrs.fr/lirmm-02148142/document

[Untitled]

Autor: Philippe Devienne, Jean-Marc Talbot, Sophie Tison

Publikováno v: Constraints. 5:161-202

Set constraints (SC) are logical formul\ae in which atoms are inclusions between set expressions. Those set expressions are built over a signature \Sigma, variables and various set operators. On a semantical point of view, the set constraints are int

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::263157f3c53029d4a1e3a5a7df2b525d
https://doi.org/10.1023/a:1009826603139

REGULAR TREE LANGUAGES AND REWRITE SYSTEMS

Autor: Sophie Tison, Rémy Gilleron

Publikováno v: Fundamenta Informaticae. 24:157-175

We present a collection of results on regular tree languages and rewrite systems. Moreover we prove the undecidability of the preservation of regularity by rewrite systems. More precisely we prove that it is undecidable whether or not for a set E of

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::7d77e2ea15d6bad4d03219c367916673
https://doi.org/10.3233/fi-1995-24127

Bounded Delay and Concurrency for Earliest Query Answering

Autor: Olivier Gauwin, Joachim Niehren, Sophie Tison

Publikováno v: 3rd International Conference on Language and Automata Theory and Applications
3rd International Conference on Language and Automata Theory and Applications, Apr 2009, Tarragona, Spain. pp.350-361, ⟨10.1007/978-3-642-00982-2⟩
Language and Automata Theory and Applications ISBN: 9783642009815
LATA

International audience; Earliest query answering is needed for streaming XML processing with optimal memory management. We study the feasibility of earliest query answering for node selection queries. Tractable queries are distinguished by a bounded

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::770fe7a9ce14fbd0f7db63e6e0472fc9
https://hal.inria.fr/inria-00348463