Zobrazeno 1 - 10
of 174
pro vyhledávání: '"Bruno Courcelle"'
Autor:
Bruno Courcelle
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 23 no. 2, special issue..., Iss Special issues (2022)
The ternary relation B(x,y,z) of betweenness states that an element y is between the elements x and z, in some sense depending on the considered structure. In a partially ordered set (N,≤), B(x,y,z):⇔x
Externí odkaz:
https://doaj.org/article/7d85493aec46492c9b2ae1b0e9ca647e
Autor:
Bruno Courcelle
Publikováno v:
Logical Methods in Computer Science, Vol Volume 17, Issue 1 (2021)
The ternary betweenness relation of a tree, B(x,y,z) expresses that y is on the unique path between x and z. This notion can be extended to order-theoretic trees defined as partial orders such that the set of nodes larger than any node is linearly or
Externí odkaz:
https://doaj.org/article/0cade5a930d4406b9ce9fd9efd74c803
Autor:
Bruno Courcelle
Publikováno v:
Logical Methods in Computer Science, Vol Volume 13, Issue 3 (2017)
Quasi-trees generalize trees in that the unique "path" between two nodes may be infinite and have any countable order type. They are used to define the rank-width of a countable graph in such a way that it is equal to the least upper-bound of the ran
Externí odkaz:
https://doaj.org/article/43eccc0cde454338a8d089f8aafec8fa
Autor:
Achim Blumensath, Bruno Courcelle
Publikováno v:
Logical Methods in Computer Science, Vol Volume 10, Issue 1 (2014)
We study the question of whether, for a given class of finite graphs, one can define, for each graph of the class, a linear ordering in monadic second-order logic, possibly with the help of monadic parameters. We consider two variants of monadic seco
Externí odkaz:
https://doaj.org/article/f3f177b8d7bd4141a632bfe903e275be
Autor:
Achim Blumensath, Bruno Courcelle
Publikováno v:
Logical Methods in Computer Science, Vol Volume 6, Issue 2 (2010)
We compare classes of finite relational structures via monadic second-order transductions. More precisely, we study the preorder where we set C \subseteq K if, and only if, there exists a transduction {\tau} such that C\subseteq{\tau}(K). If we only
Externí odkaz:
https://doaj.org/article/7066cd290eea480d962aca0d908014fa
Autor:
Bruno Courcelle
Publikováno v:
Logical Methods in Computer Science, Vol Volume 2, Issue 2 (2006)
This article establishes that the split decomposition of graphs introduced by Cunnigham, is definable in Monadic Second-Order Logic.This result is actually an instance of a more general result covering canonical graph decompositions like the modular
Externí odkaz:
https://doaj.org/article/9b7145d47572467b8db3d2ae37b3ff26
Autor:
Bruno Courcelle, Joost Engelfriet
The study of graph structure has advanced in recent years with great strides: finite graphs can be described algebraically, enabling them to be constructed out of more basic elements. Separately the properties of graphs can be studied in a logical la
Autor:
Bruno Courcelle
Publikováno v:
Journées sur les Arithmétiques Faibles
Journées sur les Arithmétiques Faibles, May 2020, Fontainebleau, France
Fields of Logic and Computation III ISBN: 9783030480059
Fields of Logic and Computation III
Journées sur les Arithmétiques Faibles, May 2020, Fontainebleau, France
Fields of Logic and Computation III ISBN: 9783030480059
Fields of Logic and Computation III
International audience; The ternary betweenness relation of a tree, B(x, y, z), indicates that y is on the unique path between x and z. This notion can be extended to order-theoretic trees defined as partial orders such that the set of nodes greater
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::eee8984b6135805c93b78c9b358c05ea
https://hal.archives-ouvertes.fr/hal-02497172
https://hal.archives-ouvertes.fr/hal-02497172
Autor:
Bruno Courcelle
Publikováno v:
Discrete Applied Mathematics. 245:236-252
A more descriptive but too long title would be : Constructing fly-automata to check properties of graphs of bounded tree-width expressed by monadic second-order formulas written with edge quantifications. Such properties are called MSO2 in short. Fly
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b01d391a2cfbaa0a6d1304e1d4ed33db
https://doi.org/10.1016/j.dam.2016.10.018
https://doi.org/10.1016/j.dam.2016.10.018
Autor:
Bruno Courcelle
Publikováno v:
Electronic Notes in Discrete Mathematics. 50:3-8
Every graph property expressible in monadic second-order (MSO) logic, can be checked in linear time on graphs of bounded tree-width by means of finite automata running on terms denoting tree-decompositions. Implementing these automata is difficult be
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::de35ae856f23b3fd1e0b9ff855e01389
https://doi.org/10.1016/j.endm.2015.07.002
https://doi.org/10.1016/j.endm.2015.07.002