Výsledky vyhledávání - "Doumane, Amina"

Report

A finite presentation of graphs of treewidth at most three

Autor: Doumane, Amina, Humeau, Samuel, Pous, Damien

We provide a finite equational presentation of graphs of treewidth at most three, solving an instanceof an open problem by Courcelle and Engelfriet.We use a syntax generalising series-parallel expressions, denoting graphs with a small interface.We in

Externí odkaz: http://arxiv.org/abs/2411.18176

Zobrazit plný text záznamu

Report

Tree algebras and bisimulation-invariant MSO on finite graphs

Autor: Colcombet, Thomas, Doumane, Amina, Kuperberg, Denis

We establish that the bisimulation invariant fragment of MSO over finite transition systems is expressively equivalent over finite transition systems to modal mu-calculus, a question that had remained open for several decades. The proof goes by trans

Externí odkaz: http://arxiv.org/abs/2407.12677

Zobrazit plný text záznamu

Report

Bouncing threads for infinitary and circular proofs

Autor: Baelde, David, Doumane, Amina, Kuperberg, Denis, Saurin, Alexis

We generalize the validity criterion for the infinitary proof system of the multiplicative additive linear logic with fixed points. Our criterion is designed to take into account axioms and cuts. We show that it is sound and enjoys the cut eliminatio

Externí odkaz: http://arxiv.org/abs/2005.08257

Zobrazit plný text záznamu

Report

First-order tree-to-tree functions

Autor: Bojańczyk, Mikołaj, Doumane, Amina

We study tree-to-tree transformations that can be defined in first-order logic or monadic second-order logic. We prove a decomposition theorem, which shows that every transformation can be obtained from prime transformations, such as tree-to-tree hom

Externí odkaz: http://arxiv.org/abs/2002.09307

Zobrazit plný text záznamu

Dissertation/ Thesis

On the infinitary proof theory of logics with fixed points

Autor: Doumane, Amina

Cette thèse traite de la theorie de la preuve pour les logiques a points fixes, telles que le μ-calcul, lalogique lineaire a points fixes, etc. ces logiques sont souvent munies de systèmes de preuves finitairesavec des règles d’induction à la

Externí odkaz: http://www.theses.fr/2017USPCC123/document

Zobrazit plný text záznamu

Bouncing threads for circular and non-wellfounded proofs -- Towards compositionality with circular proofs (Extended version)

Autor: Baelde, David, Doumane, Amina, Kuperberg, Denis, Saurin, Alexis

Publikováno v: LICS '22: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science
LICS '22: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Aug 2022, Haifa, Israel. ⟨10.1145/3531130.3533375⟩

International audience; Given that (co)inductive types are naturally modelled as fixed points, it is unsurprising that fixed-point logics are of interest in the study of programming languages, via the Curry-Howard (or proofs-as-programs) corresponden

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::8f45ed3611301020de41aab17fdf2404
https://hal.science/hal-03682126/document

Zobrazit plný text záznamu

Non-Axiomatizability of the Equational Theories of Positive Relation Algebras (Invited Talk)

Autor: Doumane, Amina

In the literature, there are two ways to show that the equational theory of relations over a given signature is not finitely axiomatizable. The first-one is based on games and a construction called Rainbow construction. This method is very technical

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

Zobrazit plný text záznamu

enGraph Characterization of the Universal Theory of Relations

Autor: Doumane, Amina

Publikováno v: Proc. MFCS
Mathematical foundations of computer science
Mathematical foundations of computer science, Aug 2021, Tallin, Estonia. ⟨10.4230/LIPIcs.MFCS.2021.11⟩

The equational theory of relations can be characterized using graphs and homomorphisms. This result, found independently by Freyd and Scedrov and by Andréka and Bredikhin, shows that the equational theory of relations is decidable. In this paper, we

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::970f3503e0a575b3688b4e16d586d695
https://doi.org/10.4230/lipics.mfcs.2021.41

Zobrazit plný text záznamu

Non axiomatisability of positive relation algebras with constants, via graph homomorphisms

Autor: Doumane, Amina, Pous, Damien

Publikováno v: CONCUR
CONCUR, 2020, Vienne, Austria. pp.1-23, ⟨10.4230/LIPIcs.CONCUR.2020.49⟩

International audience; We study the equational theories of composition and intersection on binary relations, with or without their associated neutral elements (identity and full relation). Without these constants, the equational theory coincides wit

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b1b0a33e55e2d2ab0940f4b941151dc7
https://hal.archives-ouvertes.fr/hal-02870687/file/topone.pdf

Zobrazit plný text záznamu

Completeness for Identity-free Kleene Lattices

Autor: Doumane , Amina, Pous , Damien

Publikováno v: CONCUR
CONCUR, Sep 2018, Beijing, China. ⟨10.4230/LIPIcs.CONCUR.2018.18⟩
The 29th International Conference on Concurrency Theory (CONCUR)

International audience; We provide a finite set of axioms for identity-free Kleene lattices, which we prove sound and complete for the equational theory of their relational models. Our proof builds on the completeness theorem for Kleene algebra, and

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c4750dc7e9c7bd7095a93f2f0e393d3e
https://hal.archives-ouvertes.fr/hal-01780845v2/document

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání