This article is cited in 1 scientific paper (total in 1 paper)
On solutions to systems of automata-type functional equations
S. S. Marchenkov
Lomonosov Moscow State University, Moscow, Russia
The automata-type functional equations are considered. These equations include subject variables for natural numbers and one-placed functional variables for infinite binary sequences. An algorithm is defined which solves the satisfiability problem for finite systems of functional equations containing only functions $1$ and $t+1$. The linear homogeneous structures are used to establish the lower bound for time complexity of similar deciding algorithms. It is proved that the satisfiability problem is algorithmically undecidable for the systems of functional equations which contain yet the functions $2t,3t$, and $5t$. Tab. 1, bibliogr. 10.
automata-type functional equation, satisfiability problem.
PDF file (265 kB)
S. S. Marchenkov, “On solutions to systems of automata-type functional equations”, Diskretn. Anal. Issled. Oper., 19:4 (2012), 86–98
Citation in format AMSBIB
\paper On solutions to systems of automata-type functional equations
\jour Diskretn. Anal. Issled. Oper.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
S. S. Marchenkov, “Definability in the language of functional equations of a countable-valued logic”, Discrete Math. Appl., 23:5-6 (2013), 451–462
|Number of views:|