Order:
  1.  20
    Reachability is Harder for Directed Than for Undirected Finite Graphs.Miklos Ajtai & Ronald Fagin - 1990 - Journal of Symbolic Logic 55 (1):113-150.
    Although it is known that reachability in undirected finite graphs can be expressed by an existential monadic second-order sentence, our main result is that this is not the case for directed finite graphs (even in the presence of certain "built-in" relations, such as the successor relation). The proof makes use of Ehrenfeucht-Fraisse games, along with probabilistic arguments. However, we show that for directed finite graphs with degree at most k, reachability is expressible by an existential monadic second-order sentence.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  2.  10
    Alexander S. Kechris and Alain Louveau. Descriptive Set Theory and the Structure of Sets of Uniqueness. London Mathematical Society Lecture Note Series, No. 128. Cambridge University Press, Cambridge Etc. 1987, Vii + 367 Pp. [REVIEW]Miklos Ajtai - 1991 - Journal of Symbolic Logic 56 (1):344-345.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  3.  15
    Review: Alexander S. Kechris, Alain Louveau, Descriptive Set Theory and the Structure of Sets of Uniqueness. [REVIEW]Miklos Ajtai - 1991 - Journal of Symbolic Logic 56 (1):344-345.