- Inici
- Investigació
- e-prints
- 12 - Matemàtiques
- Visualitza element
IMPORTANT: Aquest repositori està en una versió antiga des del 3/12/2023. La nova instal.lació está en https://roderic.uv.es/
K4-free graphs as a free algebra
Mostra el registre parcial de l'element
| dc.contributor.author | Cosme i Llópez, Enric | |
| dc.contributor.author | Pous, Damien | |
| dc.date.accessioned | 2019-02-27T14:25:37Z | |
| dc.date.available | 2019-02-27T14:25:37Z | |
| dc.date.issued | 2017 | |
| dc.identifier.citation | Cosme i Llópez, Enric Pous, Damien 2017 K4-free graphs as a free algebra 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) 83 76 76:1 76:14 | |
| dc.identifier.uri | http://hdl.handle.net/10550/69206 | |
| dc.description.abstract | Graphs of treewidth at most two are the ones excluding the clique with four vertices (K4) as a minor, or equivalently, the graphs whose biconnected components are series-parallel. We turn those graphs into a finitely presented free algebra,answering positively a question by Courcelle and Engelfriet, in the case of treewidth two. First we propose a syntax for denoting these graphs: in addition to parallel composition and series composition, it suffices to consider the neutral elements of those operations and a unary transpose operation. Then we give a finite equationa lpresentation and we prove it complete: two terms from the syntax are congruent if and only if they denote the same graph. | |
| dc.language.iso | eng | |
| dc.relation.ispartof | 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), 2017, vol. 83, num. 76, p. 76:1-76:14 | |
| dc.subject | Àlgebra universal | |
| dc.title | K4-free graphs as a free algebra | |
| dc.type | journal article | es_ES |
| dc.date.updated | 2019-02-27T14:25:38Z | |
| dc.identifier.doi | 10.4230/LIPIcs.MFCS.2017.76 | |
| dc.identifier.idgrec | 130223 | |
| dc.rights.accessRights | open access | es_ES |
Visualització
(513.0Kb)
Aquest element apareix en la col·lecció o col·leccions següent(s)
-
12 - Matemàtiques [287]