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/

[1] E. F. Codd, “A relational model of data for large shared data banks”, Comm. ACM, 13:6 (1970), 377–387 | DOI | Zbl

[2] E. F. Codd, “Relational completeness of data base sublanguages”, Database systems, Prentice-Hall, San Jose, 1972, 33–64

[3] A. V. Aho, J. D. Ullman, “Universality of data retrieval languages”, Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages (San Antonio, TX, 1979), ACM, New York, 1979, 110–120 | MR | Zbl

[4] P. C. Kanellakis, G. M. Kuper, P. Z. Revesz, “Constraint query languages”, J. Comput. System Sci., 51:1 (1995), 26–52 | DOI | MR

[5] S. M. Dudakov, M. A. Taitslin, “Collapse results for query languages in database theory”, Russian Math. Surveys, 61:2 (2006), 195–253 | DOI | MR | Zbl

[6] O. V. Belegradek, A. P. Stolboushkin, M. A. Taitslin, “Extended order-generic queries”, Ann. Pure Appl. Logic, 97:1–3 (1999), 85–125 | DOI | MR | Zbl

[7] J. Baldwin, M. Benedikt, “Stability theory, permutations of indiscernibles, and embedded finite models”, Trans. Amer. Math. Soc., 352:11 (2000), 4937–4969 | DOI | MR | Zbl

[8] S. M. Dudakov, “Collapse result for extensions of the Presburger arithmetic by a unary function compatible with addition”, Math. Notes, 76:3 (2004), 339–347 | DOI | MR | Zbl

[9] S. M. Dudakov, “The collapse theorem for theories of I-reducible algebraic systems”, Izv. Math., 68:5 (2004), 911–933 | DOI | MR | Zbl

[10] M. Benedikt, L. Libkin, “Expressive power: the finite case”, Constraint databases, Berlin, 1996, 55–87

[11] M. Benedikt, G. Dong, L. Libkin, L. Wong, “Relational expressive power of constraint query languages”, J. ACM, 45:1 (1998), 1–34 | DOI | MR | Zbl

[12] S. M. Dudakov, “Vyrazitelnaya sila yazykov zaprosov pervogo poryadka dlya baz dannykh na neuporyadochennom sluchainom grafe”, Vestn. NovGU, 34 (2005), 51–57

[13] M. Otto, J. Van den Bussche, “First-order queries on databases embedded in an infinite structure”, Inform. Process. Lett., 60:1 (1996), 37–41 | DOI | MR | Zbl

[14] S. M. Dudakov, “Razreshimaya teoriya bez translyatsionnoi teoremy”, Vestn. TvGU. Ser. Prikladnaya matem., 6:12 (2005), 23–26

[15] R. Rado, “Universal graphs and universal functions”, Acta Arith., 9 (1964), 331–340 | MR | Zbl

[16] A. K. Chandra, D. Harel, “Computable queries for relational data bases”, J. Comput. System Sci., 21:2 (1980), 156–178 | DOI | MR | Zbl

[17] B. A. Trakhtenbrot, Ya. M. Barzdin', Finite automata. Behavior and synthesis, North-Holland, Amsterdam–London, 1973 | MR | MR | Zbl | Zbl

[18] W. Brauer, Automatentheorie, Leitfaden Monogr. Inform., Teubner, Stuttgart, 1984 | MR | Zbl