RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Subscription Guidelines for authors License agreement Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Mat. Zametki: Year: Volume: Issue: Page: Find

 Personal entry: Login: Password: Save password Enter Forgotten password? Register

 Mat. Zametki, 1972, Volume 11, Issue 6, Pages 687–697 (Mi mz9837)

This article is cited in 7 scientific papers (total in 7 papers)

On the algorithmic undecidability of $A$-completeness for the boundedly determinate functions

V. A. Buevich

Computation Center, Academy of Sciences of the USSR

Abstract: A functional system $P$ is considered, whose elements are functions realized by the so-called finite automata and known as the boundedly determinate functions (B. D. functions) and whose operations are known as the operations of superposition. The system $\mathfrak{M}$ of B.D. functions is called $A$-complete if, for an arbitrary B. D. function and for every natural number $\tau>0$, we can obtain (with the help of the operations of superposition) a B. D. function coinciding with the given one of all the words of lenth $\tau$ from the B. D. functions of the system $\mathfrak{M}$. The question is: does there exist an algorithm for deciding the $A$-completeness of an arbitrary finite system of B. D. functions? It is shown that such an algorithm does not exist (see [4]).

Full text: PDF file (1445 kB)

English version:
Mathematical Notes, 1972, 11:6, 417–421

Bibliographic databases:

UDC: 519.9
Received: 17.03.1971

Citation: V. A. Buevich, “On the algorithmic undecidability of $A$-completeness for the boundedly determinate functions”, Mat. Zametki, 11:6 (1972), 687–697; Math. Notes, 11:6 (1972), 417–421

Citation in format AMSBIB
\Bibitem{Bue72} \by V.~A.~Buevich \paper On the algorithmic undecidability of $A$-completeness for the boundedly determinate functions \jour Mat. Zametki \yr 1972 \vol 11 \issue 6 \pages 687--697 \mathnet{http://mi.mathnet.ru/mz9837} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=313028} \zmath{https://zbmath.org/?q=an:0265.02032|0251.02047} \transl \jour Math. Notes \yr 1972 \vol 11 \issue 6 \pages 417--421 \crossref{https://doi.org/10.1007/BF01093729} 

Linking options:
• http://mi.mathnet.ru/eng/mz9837
• http://mi.mathnet.ru/eng/mz/v11/i6/p687

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. V. B. Kudryavtsev, “Automata algebras”, J. Math. Sci., 169:4 (2010), 435–456
2. M. A. Podkolzina, “On completeness and $A$-completeness of $S$-sets of determinate functions containing all one-place determinate $S$-functions”, Discrete Math. Appl., 19:3 (2009), 263–276
3. D. N. Zhuk, “On the classification of Post automaton bases by the decidability of the $A$-completeness property for definite automata”, Discrete Math. Appl., 20:3 (2010), 337–355
4. Zhuk D.N., “Kriterii razreshimosti problemy a-polnoty dlya definitnykh avtomatov”, Doklady Akademii nauk, 439:1 (2011), 18–20
5. V. A. Buevich, M. A. Podkolzina, “On algorithmic solvability of the $A$-completeness problem for systems of boundedly determinate functions containing all one-place boundedly determinate $S$-functions”, Discrete Math. Appl., 22:5-6 (2012), 555–569
6. I. E. Ivanov, “Ob avtomatnykh funktsiyax s magazinnoi pamyatyu”, Intellektualnye sistemy. Teoriya i prilozheniya, 22:1 (2018), 39–110
7. A. A. Chasovskikh, “Problema polnoty v klassakh lineinykh avtomatov”, Intellektualnye sistemy. Teoriya i prilozheniya, 22:2 (2018), 151–153
•  Number of views: This page: 117 Full text: 51 First page: 1

 Contact us: math-net2020_10 [at] mi-ras ru Terms of Use Registration Logotypes © Steklov Mathematical Institute RAS, 2020