Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Branch-width, parsovací stromy a monadická logika druhého řádu pro matroidy
Autoři	HLINĚNÝ Petr
Rok publikování	2006
Druh	Článek v odborném periodiku
Časopis / Zdroj	Journal of Combinatorial Theory, Ser B
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	http://dx.doi.org/10.1016/j.jctb.2005.08.005
Obor	Obecná matematika
Klíčová slova	matroid representation; branch-width; monadic second-order logic; tree automaton; fixed-parameter complexity
Popis	Článek dokazuje obdobu tzv. MS2-věty pro matroidy reprezentované nad konečnými tělesy: Pro matroid reprezentovaný nad konečným tělesem s omezenou branch-width lze stromovými automaty rozhodnout všechny MSO definované vlastnosti.
Související projekty:	Vysoce paralelní a distribuované výpočetní systémy