Geodesic
On the application of finite-state machines to the investigation of the fixed-point theory decidability
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 1 (2016), pp. 103-115 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We investigate effective elimination of the fixed point operator in a theory of integers with a single successor function. We construct a finite-state machine for a language containing words matching the least fixed point.
Keywords: decidability, fixed point operator, finite-state machine. 
@article{VTPMK_2016_1_a7,
     author = {A. S. Zolotov},
     title = {On the application of finite-state machines to the investigation of the fixed-point theory decidability},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {103--115},
     year = {2016},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2016_1_a7/}
}
TY  - JOUR
AU  - A. S. Zolotov
TI  - On the application of finite-state machines to the investigation of the fixed-point theory decidability
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2016
SP  - 103
EP  - 115
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2016_1_a7/
LA  - ru
ID  - VTPMK_2016_1_a7
ER  - 
%0 Journal Article
%A A. S. Zolotov
%T On the application of finite-state machines to the investigation of the fixed-point theory decidability
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2016
%P 103-115
%N 1
%U http://geodesic.mathdoc.fr/item/VTPMK_2016_1_a7/
%G ru
%F VTPMK_2016_1_a7
A. S. Zolotov. On the application of finite-state machines to the investigation of the fixed-point theory decidability. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 1 (2016), pp. 103-115. http://geodesic.mathdoc.fr/item/VTPMK_2016_1_a7/

[1] Blumensath A., Graedel E., “Automatic structures”, Proc. of 15th IEEE Symposium on Logic in Computer Science, 2000, 51–62 | MR

[2] Boolos G. S., Jefferey R. C., Computability and Logic, Cambridge University Press, 1994 | MR

[3] Church A., “A note on the Entscheidungs problem”, The Journal of Symbolic Logic, 1936, no. 1, 40–41 | DOI

[4] Church A., “An unsolvable problem of elementary number theory”, American Journal of Mathematics, 58 (1936), 345–363 | DOI | MR

[5] Dudakov S. M., “On inflationary fix-point operators safety”, Lobachevskii Journal of Mathematics, 36:4 (2015), 328–331 | DOI | MR | Zbl

[6] Gurevich Y., Shelah S., “Fixed-point extensions of first-order logic”, Annals of Pure and Applied Logic, 32 (1986), 265–280 | DOI | MR | Zbl

[7] Presburger M., “Uber die Vollstandigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt”, Comptes Rendus du I congres de Mathematiciens des Pays Slaves (Warszawa, 1929), 92–101 | Zbl

[8] Rabin M. O., “Decidability of second-order theories and automata on infinite trees”, Transactions of the American Mathematical Society, 141:7 (1969), 1–35 | MR | Zbl

[9] Zolotov A. S., “On decidability of the theory with the transitive closure operator”, Lobachevskii Journal of Mathematics, 36:4 (2015), 434–440 | DOI | MR | Zbl

[10] Dudakov S. M., “Monadic structures over an ordered universal random graph and finite automata”, Izvestiya: Mathematics, 75:5 (2011), 915–932 | DOI | DOI | MR | Zbl

[11] Dudakov S. M., “On safety of recursive queries”, Vestnik TvGU. Seriya: Prikladnaya Matematika [Herald of Tver State University. Series: Applied Mathematics], 2012, no. 4(27), 71–80 (in Russian)

[12] Dudakov S. M., “On safety of IFP-operators and recursive queries”, Vestnik TvGU. Seriya: Prikladnaya Matematika [Herald of Tver State University. Series: Applied Mathematics], 2013, no. 2(29), 5–13 (in Russian)

[13] “On undecidability of definiteness of binary IFP-operators for one successor function theory”, Vestnik TvGU. Seriya: Prikladnaya Matematika [Herald of Tver State University. Series: Applied Mathematics], 2014, no. 4, 7–15 (in Russian)

[14] Zolotov A. S., “The use of the transitive closure operator on formulas with a single successor function and divisibility predicates”, Vestnik TvGU. Seriya: Prikladnaya Matematika [Herald of Tver State University. Series: Applied Mathematics], 2013, no. 1(28), 101–117 (in Russian)

[15] Zolotov A. S., “On undecidability of additive and multiplicative theories of natural numbers with the transitive closure operator”, Vestnik TvGU. Seriya: Prikladnaya Matematika [Herald of Tver State University. Series: Applied Mathematics], 2014, no. 3, 117–124 (in Russian)

[16] Zolotov A. S., “On the elimination of fixed point operator for some formulas in a theory of single successor function”, Vestnik TvGU. Seriya: Prikladnaya Matematika [Herald of Tver State University. Series: Applied Mathematics], 2015, no. 4, 27–37 (in Russian) | MR