J 2006

Trees, grids, and MSO decidability: From graphs to matroids

HLINĚNÝ, Petr and Detlef SEESE

Basic information

Original name

Trees, grids, and MSO decidability: From graphs to matroids

Name in Czech

Stromy, mříže a MSO rozhodnutelnost: Od grafů k matroidům

Authors

HLINĚNÝ, Petr (203 Czech Republic, guarantor) and Detlef SEESE (276 Germany)

Edition

Theoretical Computer Science, Amsterdam, Elsevier, 2006, 0304-3975

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

References:

Impact factor

Impact factor: 0.843

RIV identification code

RIV/00216224:14330/06:00015570

Organization unit

Faculty of Informatics

UT WoS

000235646800008

Keywords in English

matroid; branch-width; MSO theory; decidability

Tags

Tags

International impact, Reviewed
Změněno: 16/11/2006 11:49, prof. RNDr. Petr Hliněný, Ph.D.

Abstract

ORIG CZ

V originále

We show that, for every finite field $\pf F$, the class of all $\pf F$-representable matroids of branch-width at most a constant~$t$ has a decidable MSO theory. In the other direction, we prove that every class of $\pf F$-representable matroids with a decidable MSO theory must have uniformly bounded branch-width.

In Czech

Dokazujeme, že na každým konečným tělesem má třída všech reprezentovatelných matroidů omezené branch-width rozhodnutelnou MSO teorii. Naopak každá taková třída reprezentovatelných matroidů s rozhodnutelnou MSO teorií musí mít omezenou branch-width.

Links

GA201/05/0050, research and development project
Name: Strukturální vlastnosti a algoritmická složitost diskrétních problémů
MSM0021622419, plan (intention)
Name: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems