Informace o publikaci
Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids
| Název česky | Branch-width, parsovací stromy a monadická logika druhého řádu pro matroidy |
|---|---|
| Autoři | |
| Rok publikování | 2006 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Journal of Combinatorial Theory, Ser B |
| Fakulta / Pracoviště MU | |
| 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: |