Lower Bounds on the Complexity of MSO1 Model-Checking

Ganian, Robert; Hlinený, Petr; Langer, Alexander; Obdrzálek, Jan; Rossmanith, Peter; Sikdar, Somnath

by Robert Ganian, Petr Hlinený, Alexander Langer, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar

Reference:

Lower Bounds on the Complexity of MSO1 Model-CheckingRobert Ganian, Petr Hlinený, Alexander Langer, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France, volume 14 of LIPIcs, pages 326–337, 2012, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.

Bibtex Entry:

@string{lipics="LIPIcs"}
@inproceedings{GanianHLOR12,
  author    = {Robert Ganian and
               Petr Hlinen{\'{y}} and
               Alexander Langer and
               Jan Obdrz{\'{a}}lek and
               Peter Rossmanith and
               Somnath Sikdar},
  title     = {Lower Bounds on the Complexity of MSO1 Model-Checking},
  booktitle = {29th International Symposium on Theoretical Aspects of Computer Science,
               {STACS} 2012, February 29th - March 3rd, 2012, Paris, France},
  pages     = {326--337},
  year      = {2012},
  series    = {LIPIcs},
  volume    = {14},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}
}