Using models to model-check recursive schemes

Autor: Sylvain Salvati, Igor Walukiewicz

Publikováno v: Logical Methods in Computer Science, Vol Volume 11, Issue 2 (2015)

We propose a model-based approach to the model checking problem for recursive schemes. Since simply typed lambda calculus with the fixpoint operator, lambda-Y-calculus, is equivalent to schemes, we propose the use of a model of lambda-Y-calculus to d

Externí odkaz: https://doaj.org/article/d9c0be4f583a49bcb6bbd673c9ca49ad

On is an n-MCFL

Autor: Kilian Gebhardt, Frédéric Meunier, Sylvain Salvati

Publikováno v: Journal of Computer and System Sciences
Journal of Computer and System Sciences, 2022, 127, pp.41-52. ⟨10.1016/j.jcss.2022.02.003⟩

International audience; Commutative properties in formal languages pose problems at the frontier of computer science, computational linguistics and computational group theory. A prominent problem of this kind is the position of the language $O_n$, th

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2ae86b5d5decdce7eeaf2c77977f7171
https://hal.science/hal-01771670v2/file/MCFL.pdf

The Diagonal Problem for Higher-Order Recursion Schemes is Decidable

Autor: Lorenzo Clemente, Paweł Parys, Igor Walukiewicz, Sylvain Salvati

Publikováno v: LICS
LICS, Jun 2016, New York, United States. pp.96-105, ⟨10.1145/2933575.2934527⟩

A non-deterministic recursion scheme recognizes a language of finite trees. This very expressive model can simulate, among others, higher-order pushdown automata with collapse. We show decidability of the diagonal problem for schemes. This result has

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::06ee6a86b02c6021d309b1c3ad464212
https://doi.org/10.1145/2933575.2934527

A logical approach to grammar description

Autor: Jérôme Kirman, Sylvain Salvati, Lionel Clément

Publikováno v: Journal of Language Modelling
Journal of Language Modelling, Institute of Computer Science, Polish Academy of Sciences, Poland, 2015, Special issue on High-level methodologies for grammar engineering, 3 (1), pp. 87-143 ⟨10.15398/jlm.v3i1.94⟩
Journal of Language Modelling, Vol 3, Iss 1 (2015)
Journal of Language Modelling, 2015, Special issue on High-level methodologies for grammar engineering, 3 (1), pp. 87-143 ⟨10.15398/jlm.v3i1.94⟩

International audience; In the tradition of Model Theoretic Syntax, we propose a logical approach to the description of grammars. We combine in one formalism several tools that are used throughout computer science for their power of abstraction: logi

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::77a56913c4c0fed39a9a818f14a20783
https://hal.archives-ouvertes.fr/hal-01251222/file/cks.pdf

Non-linear Second order Abstract Categorial Grammars and deletion

Autor: Sylvain Salvati

Publikováno v: NLCS 2015: Natural Language and Computer Science
NLCS 2015: Natural Language and Computer Science, Makoto Kanazawa, 2015, Kyoto, Japan
NLCS@ICALP/LICS

International audience; We prove that non-linear second order Abstract Categorial Grammars (2ACGs) are equivalent to non-deleting 2ACGs. We prove this result first by using the intersection types discipline. Then we explain how coherence spaces can y

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::824c9c957ccea5f906e04700bc36aa27
https://hal.archives-ouvertes.fr/hal-01251127/file/lambda_i.pdf