Аннотация:
В работе изучается проблема разрушения для логических языков, предназначенных для описания свойств одноместных функций ff на натуральном ряде NN. Для функций ff, принимающих конечное число значений, получен критерий разрешимости монадической теории структуры ⟨N;⩽,f⟩. Для широкого класса монотонных функций f найдены условия, при которых элементарная теория структуры ⟨N;⩽,f⟩ разрешима; соответствующие условия найдены также для структур вида ⟨N;+,f⟩.
Библиография: 20 названий.
Образец цитирования:
А. Л. Семёнов, “Логические теории одноместных функций на натуральном ряде”, Изв. АН СССР. Сер. матем., 47:3 (1983), 623–658; Math. USSR-Izv., 22:3 (1984), 587–618
\RBibitem{Sem83}
\by А.~Л.~Семёнов
\paper Логические теории одноместных функций на натуральном ряде
\jour Изв. АН СССР. Сер. матем.
\yr 1983
\vol 47
\issue 3
\pages 623--658
\mathnet{http://mi.mathnet.ru/im1415}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=703597}
\zmath{https://zbmath.org/?q=an:0541.03005}
\transl
\jour Math. USSR-Izv.
\yr 1984
\vol 22
\issue 3
\pages 587--618
\crossref{https://doi.org/10.1070/IM1984v022n03ABEH001456}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/im1415
https://www.mathnet.ru/rus/im/v47/i3/p623
Эта публикация цитируется в следующих 39 статьяx:
Hao Wu, Yu-Fang Chen, Zhilin Wu, Bican Xia, Naijun Zhan, “A decision procedure for string constraints with string/integer conversion and flat regular constraints”, Acta Informatica, 61:1 (2024), 23
Valérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, James Worrell, Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024, 1
Valérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, James Worrell, “The monadic theory of toric words”, Theoretical Computer Science, 2024, 114959
Christian Servin, Olga Kosheleva, Vladik Kreinovich, Studies in Systems, Decision and Control, 484, Uncertainty, Constraints, and Decision Making, 2023, 135
Richard Mandel, Alexander Ushakov, “The Diophantine problem for systems of algebraic equations with exponents”, Journal of Algebra, 636 (2023), 779
Toghrul Karimov, Edon Kelmendi, Joris Nieuwveld, Joël Ouaknine, James Worrell, 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2023, 1
Toghrul Karimov, Engel Lefaucheux, Joël Ouaknine, David Purser, Anton Varonka, Markus A. Whiteland, James Worrell, “What's decidable about linear loops?”, Proc. ACM Program. Lang., 6:POPL (2022), 1
Shaull Almagor, Toghrul Karimov, Edon Kelmendi, Joël Ouaknine, James Worrell, “Deciding ω-regular properties on linear recurrence sequences”, Proc. ACM Program. Lang., 5:POPL (2021), 1
Ф. А. Дудкин, А. В. Трейер, “Задача о рюкзаке для групп Баумслага–Солитера”, Сиб. журн. чист. и прикл. матем., 18:4 (2018), 43–55
Н. Н. Корнеева, “Автоматные преобразования префиксно разрешимых и разрешимых по Бюхи сверхслов”, Изв. вузов. Матем., 2016, № 7, 55–65; N. N. Korneeva, “Automata transformations of prefix decidable and decidable by Buchi superwords”, Russian Math. (Iz. VUZ), 60:7 (2016), 47–55
Francesco Alberti, Silvio Ghilardi, Natasha Sharygina, “Decision Procedures for Flat Array Properties”, J Autom Reasoning, 2015
Alberti F., Ghilardi S., Sharygina N., “A New Acceleration-Based Combination Framework for Array Properties”, Frontiers of Combining Systems, Lecture Notes in Computer Science, 9322, eds. Lutz C., Ranise S., Springer-Verlag Berlin, 2015, 169–185
Francesco Alberti, Silvio Ghilardi, Natasha Sharygina, Lecture Notes in Computer Science, 8413, Tools and Algorithms for the Construction and Analysis of Systems, 2014, 15
М. Н. Вялый, А. А. Рубцов, “Алгоритмическая разрешимость задач о поведении автоматов на сверхсловах”, Дискретн. анализ и исслед. опер., 19:2 (2012), 3–18
Alexander Rabinovich, “The Church problem for expansions of by unary predicates”, Information and Computation, 2012
Alla Sirokofskich, “Decidability questions for a ring of Laurent polynomials”, Annals of Pure and Applied Logic, 2011
Alexis Bès, Alexander Rabinovich, Bruno Courcelle, “Decidable Expansions of Labelled Linear Orderings”, Log.Meth.Comput.Sci, 7:2 (2011)
Ю. Л. Притыкин, “Почти периодичность, конечно-автоматные преобразования и вопросы эффективности”, Изв. вузов. Матем., 2010, № 1, 74–87; Yu. L. Pritykin, “Almost periodicity, finite automata mappings, and related effectiveness issues”, Russian Math. (Iz. VUZ), 54:1 (2010), 59–69
А. С. Снятков, “Разрешимость теории Th(ω,0,1,<,+,f0,…,fn)”, Модел. и анализ информ. систем, 17:3 (2010), 72–90
Alla Sirokofskich, “On an exponential predicate in polynomials over finite fields”, Proc. Amer. Math. Soc., 138:7 (2010), 2569
Цитирование в формате AMSBIB
Обратная связь: