K4-free graphs as a free algebra
NAGIOS: RODERIC FUNCIONANDO

K4-free graphs as a free algebra

DSpace Repository

K4-free graphs as a free algebra

Show simple item record

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.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.rights.uri info:eu-repo/semantics/openAccess
dc.source 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.subject Àlgebra universal
dc.title K4-free graphs as a free algebra
dc.type info:eu-repo/semantics/article
dc.date.updated 2019-02-27T14:25:38Z
dc.identifier.doi https://doi.org/10.4230/LIPIcs.MFCS.2017.76
dc.identifier.idgrec 130223

View       (513.0Kb)

This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search

Browse

Statistics