Paper Info
Title
Regular languages of words over countable linear orderings
Abstract
We develop an algebraic model for recognizing languages of words indexed by countable linear orderings. This notion of recognizability is effectively equivalent to definability in monadic second-order (MSO) logic. The proofs also imply the first known collapse result for MSO logic over countable linear orderings.
Year
Venue
Keywords
2011
ICALP'11 Proceedings of the 38th international conference on Automata, languages and programming - Volume Part II
known collapse result,algebraic model,countable linear ordering,monadic second-order,regular language,mso logic
Field
DocType
Volume
Discrete mathematics,Combinatorics,Countable set,Algebraic model,Linear ordering,Algebra,Automaton,Mathematical proof,Regular language,Expressive power,Mathematics,Monad (functional programming)
Conference
abs/1702.05342
ISSN
Citations 
PageRank 
0302-9743
8
0.81
References 
Authors
2
3
Name
Order
Citations
PageRank
Olivier Carton138140.97
Thomas Colcombet232731.61
Gabriele Puppis321220.49