"Записки научных семинаров ПОМИ"
VOL. 358
"Исследования по конструктивной математике и
математической логике. XI"
редактор М.А. Всемирнов
Contents
- Алмейда Ж., Волков И.В., Гольдберг С.В.
Сложность задачи проверки тождеств
в конечных полугруппах
....... 5(.ps.gz)
- Бес А., Сежельски П.
Немаксимальные разрешимые структуры
....... 23(.ps.gz)
- Гессарян И., Сежельски П.
Включения деревьев в окна и сечения
....... 38(.ps.gz)
- Гирш Э.А., Григорьев Д.Ю., Первышев К.В.
Иерархии по времени с неравномерной подсказкой для
криптографического обращения функций
....... 54(.ps.gz)
- Гордеев Л., Хойслер Е.Г., да Коста В.Г.
Сжатие доказательств при помощи циклически структурированных
подстановок
....... 77(.ps.gz)
- Григорьефф С., Шоффру К.
Проблемы разрешимости для некоторых логик конечных
слов над бесконечными алфавитами
....... 100(.ps.gz)
- Дурнев В. Г., Зеткина О. В.
Об уравнениях с ограничениями на решения
в свободных полугруппах
....... 120(.ps.gz)
- Заславский И. Д.
Нечеткая конструктивная логика
....... 130(.ps.gz)
- Каваньетто С.
Длины доказательств: гипотеза Крайзеля и теорема
Геделя об ускорении
....... 153(.ps.gz)
- Кановей В. Г., Любецкий В. А.
Борелевская сводимость как аддитивное свойство областей
....... 189(.ps.gz)
- Корнелиссен Г., Шляпентох А.
Определение целых в больших кольцах числовых полей при помощи одного
квантора общности
....... 199(.ps.gz)
- Крейнович В., Маргенштерн М.
В некоторых искривленных пространствах NP-трудные задачи разрешимы за
полиномиальное время
....... 224(.ps.gz)
- Минц Г., Хоши Т.
Логические уравнения в логике одноместных предикатов
....... 251(.ps.gz)
- Скордев Д.
Об одном классе базисов булевых функций
....... 271(.ps.gz)
- Тискин А.
Быстрое распознавание подпоследовательностей в сжатых строках
....... 282(.ps.gz)
-
Рефераты ....... 301
(.ps.gz)
Contents
- Almeida J., Volkov M. V., Goldberg S. V.
Complexity of the identity checking problem
for finite semigroups
....... 5
- B\`es A., C\'egielski P.
Non-maximal decidable structures
....... 23
- Guessarian I., C\'egielski P.
Tree inclusions in windows and slices
....... 38
- Hirsch E. A.,Grigoriev D. Yu., Pervyshev K. V.
Time hierarchies
for cryptographic function inversion
with advice
....... 54
- Gordeev L., Haeusler E. H., da Costa V. G.
Proof compressions with circuit-structured substitutions
....... 77
- Grigorieff S., Choffrut Ch.
The decision problem for some logics
for finite words on infinite alphabets
....... 100
- Durnev V., Zetkina O. On equations in free semigroups with certain
constraints on their solutions
....... 120
- Zaslavsky I. D. Fuzzy constructive logic
....... 130
- Cavagnetto S.
The Lengths of Proofs Kreisel's conjecture
and G\"odel's speed-up theorem
....... 153
- Kanovei V., Lyubetsky V.
Borel reducibility as an additive property of domains
....... 189
- Cornelissen G., Shlapentokh A.
Defining the integers in large rings of a number
field using one universal quantifier
....... 199
- Kreinovich V., Margenstern M.
In some curved spaces, one can solve NP-hard
problems in polynomial time
....... 224
- Mints G., Hoshi T.
Logical equations in monadic logic
....... 251
- Skordev D.
On a class of bases for Boolean functions
....... 271
- Tiskin A.
Faster subsequence recognition in compressed strings
....... 282
-
Reviews ....... 301
Paging: 306 pp.
-
Back to the Petersburg Department of
Steklov Institute of Mathematics