A. S. Zolotov, “On the application of finite-state machines to the investigation of the fixed-point theory decidability”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2016, Issue 1,Pages <nobr>103

Theoretical Foundations of Computer Science

On the application of finite-state machines to the investigation of the fixed-point theory decidability

A. S. Zolotov

Tver State University

Abstract: 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.

UDC: 533.6, 517.95

Received: 15.01.2016
Revised: 08.02.2016