Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Marked Items 
Alerts
Order History
Saved Items
All
Favorites
    
Book Chapter Printable view
Monadic second-order logic and linear orderings of finite structures

Monadic second-order logic and linear orderings of finite structures

Book SeriesLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
ISSN0302-9743 (Print) 1611-3349 (Online)
VolumeVolume 933/1995
BookComputer Science Logic
DOI10.1007/BFb0022242
Copyright1995
ISBN978-3-540-60017-6
DOI10.1007/BFb0022254
Pages163-176
Subject CollectionComputer Science
SpringerLink DateMonday, April 10, 2006
Add to marked items

Monadic second-order logic and linear orderings of finite structures

Bruno Courcelle1 Contact Information

(1)  LaBRI, Université Bordeaux-I, 351, Cours de la Libération, 33405 Talence Cedex, France
Abstract
We consider graphs in which it is possible to specify linear orderings of the sets of vertices, in uniform ways, by MS (i.e., Monadic Second-order) formulas. We also consider classes of graphs Copf such that for every L $$\subseteq$$ Copf, L is recognizable iff it is MS-definable. Our results concern in particular dependency graphs of partially commutative words.

Contact Information Bruno Courcelle (Laboratoire associé au CNRS)
Email: courcell@labri.u-bordeaux.fr
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.
more options
Find


Export this chapter
Export this chapter as RIS | Text
 
Frequently asked questions | General information on journals and books | Send us your feedback | Impressum | Contact
© Springer. Part of Springer Science+Business Media
Privacy, Disclaimer, Terms and Conditions, © Copyright Information
Remote Address: 38.107.191.113 • Server: mpweb24
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)