Geodesic
Monadic structures over an ordered universal random graph and finite automata
Izvestiya. Mathematics , Tome 75 (2011) no. 5, pp. 915-932

Voir la notice de l'article provenant de la source Math-Net.Ru

We continue the investigation of the expressive power of the language of predicate logic for finite algebraic systems embedded in infinite systems. This investigation stems from papers of M. A. Taitslin, M. Benedikt and L. Libkin, among others. We study the properties of a finite monadic system which can be expressed by formulae if such a system is embedded in a random graph that is totally ordered in an arbitrary way. The Büchi representation is used to connect monadic structures and formal languages. It is shown that, if one restricts attention to formulae that are $$-invariant in totally ordered random graphs, then these formulae correspond to finite automata. We show that $=$-invariant formulae expressing the properties of the embedded system itself can express only Boolean combinations of properties of the form ‘the cardinality of an intersection of one-place predicates belongs to one of finitely many fixed finite or infinite arithmetic progressions’.
Keywords: universal random graph, first-order logic, automaton language. 
@article{IM2_2011_75_5_a2,
     author = {S. M. Dudakov},
     title = {Monadic structures over an ordered universal random graph and finite automata},
     journal = {Izvestiya. Mathematics },
     pages = {915--932},
     publisher = {mathdoc},
     volume = {75},
     number = {5},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2011_75_5_a2/}
}
TY  - JOUR
AU  - S. M. Dudakov
TI  - Monadic structures over an ordered universal random graph and finite automata
JO  - Izvestiya. Mathematics 
PY  - 2011
SP  - 915
EP  - 932
VL  - 75
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_2011_75_5_a2/
LA  - en
ID  - IM2_2011_75_5_a2
ER  - 
%0 Journal Article
%A S. M. Dudakov
%T Monadic structures over an ordered universal random graph and finite automata
%J Izvestiya. Mathematics 
%D 2011
%P 915-932
%V 75
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_2011_75_5_a2/
%G en
%F IM2_2011_75_5_a2
S. M. Dudakov. Monadic structures over an ordered universal random graph and finite automata. Izvestiya. Mathematics , Tome 75 (2011) no. 5, pp. 915-932. http://geodesic.mathdoc.fr/item/IM2_2011_75_5_a2/