Straubing H. — Finite automata, format logic, and circuit complexity :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Straubing H. — Finite automata, format logic, and circuit complexity

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Finite automata, format logic, and circuit complexity

Автор: Straubing H.

Аннотация:

The study of the connections between mathematical automata and formal logic is as old as theoretical computer science itself. In the founding paper of the subject, published in 1936, Turing showed how to describe the behavior of a universal computing machine with a formula of first-order predicate logic, and thereby concluded that there is no algorithm for deciding the validity of sentences in this logic. Research on the logical aspects of the theory of finite-state automata, which is the subject of this book, began in the early 1960's with the work of J. Richard Biichi on monadic second-order logic.

Язык:

Рубрика: Computer science/Вычислимость/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1994

Количество страниц: 225

Добавлена в каталог: 23.11.2005

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

$(FO + MOD)[\mathcal{C}]$       101
$(FO + MOD)[\mathcal{N}]$       162
      137
-reducibility      139
      2
      2
$A^{\omega}$       28
$C_n(\phi)$       66
      137
      137
$FO[\empty]$       76
$FO[\mathcal{N}]$       161
$MOD(q)[\mathcal{N}]$       162
$MOD[\mathcal{C}]$ , $MOD(\mathcal{P})[\mathcal{C}]$       101
      137
, complete languages      159
, regular languages in      155
$\mathcal{E}(S)$       67
$\mathcal{J}$ -class      180
$\mathcal{J}$ -equivalence      179
$\mathcal{L}$ -class      180
$\mathcal{L}$ -equivalence      179
$\prod_k$ -formula      18 84
(FO + MOD)[+l]      107—111
(FO + MOD)[<]      102—107
(FO + MOD)[Reg\      117—118
Abelian normal series      102
ACC      140
action      61
Alphabet      1
Aperiodic monoid      59
Atomic formula      11
Automaton      2
Automaton, deterministic      3
Automaton, minimal      4
Automaton, nondeterministic      2
Automaton, on infinite words      29
Base monoid in category      70
Bilateral semidirect product      62
Block product      64
Bound variable      12
Branching program      176
Category      66—71
Category, arrows in      66
Category, base monoid in      70
Category, coterminal paths in      68
Category, covering      68
Category, objects in      66
Category, strongly connected      70
CC      141
Chinese remainder theorem      135
Circuit for addition      127—128
Circuit for division      151
Circuit for iterated addition      129—130
Circuit for iterated addition with few summands      130
Circuit for iterated multiplication      133—135
Circuit for majority      130 132
Circuit for multiplication      130
Circuit, definition      135
Circuit, depth of      128 136
Circuit, size of      135
Complete languages for       159
Congruence      6
Congruence, syntactic      54
Coterminal paths in a category      68
Covering of categories      68
Cyclic semigroup      180
Decidable theory      34—35
Depth of circuit      128 136
Deterministic automaton      3
Division of monoids      56
Division of semigroups      57
Division of tss      183
Dot-depth hierarchy      98
Ehrenfeucht — Fraisse game      39—44
Ehrenfeucht — Fraisse game for modular quantifiers      125
Empty word      2
Equivalence, logical equivalence of formulas      40
Equivalent formulas      15
Factor      2
Fan-in      128 136
Fan-out      136
First-order formula      10—12
First-order formula, semantics of      13—17
FO[+l]      46—50 88
FO[<]      44—46 59—61 79
FO[<], hierarchy in      84—88
FO[=]      76
FO[Reg]      93—97
Free monoid      7
Free semigroup      7
Free variable      12
Group, simple nonabelian      156

Group, solvable      102
Homomorphism      6
Homomorphism of monoids      7
Ideal in semigroup      179
Idempotent      6
Infinite string      28
Infinite word      28
Interpretation      13
Kleene’s Theorem      5
Krohn — Rhodes Theorem      65
Language      2
Language, $\omega$ -language      29
Language, defined by a formula      15
Language, locally testable      47
Language, locally threshold testable      47
Language, rational      8
Language, recognizable      8
Language, regular      3
Language, star-free      76 97
Left-simple semigroup      178
Left-zero semigroup      179
Locally testable language      47
Locally threshold testable language      47
Majority circuit      130—133
Minimal automaton      4
Model      14
Model theory      19
Modular quantifiers      99—102
MOD[+1]      111—116
MOD[<], $MOD(\mathcal{P})[<]$       103—107
MOD[Reg]      118—121
Monadic numerical predicates      172
Monadic predicate      10
Monadic second-order formula      10 12 21
Monadic second-order formula, existential      24
Monadic second-order formula, semantics of      17
Monoid      7
Monoid homomorphism      7
Monoid, aperiodic      59
Monoid, free      7
Monoid, syntactic      54—58
Monoid, transition monoid of automaton      55
Morphism, syntactic      54
Nondeterministic automaton      2
Numerical predicate      11
Numerical predicate, bit predicate      178
Numerical predicate, monadic      172
Numerical predicate, regular      25—28 93
Numerical predicates, arbitrary      161
Numerical relation      13
One-scan program      172
Polynomial representation of boolean functions      143
Predicate      10
Predicate, monadic      10
Predicate, numerical      11
Prefix      2
Prefix form      18
Presburger arithmetic      36
Prime number theorem      134
Program, branching      178
Program, one-scan      172
Program, over a finite monoid      176
Pseudovariety      71—75
Quantifier complexity      39—40
Quasi-aperiodic homomorphism      93
Quotient semigroup      6
Rational language      8
Recognition by a circuit      136
Recognition by a homomorphism      56
Recognition by a monoid      56
Recognition by a semigroup      57
Recognizable language      8
Reducibility      132
Reducibility,       139
Reducibility, even stronger      160
Reducibility, strong      141 159
Regular expression      5
Regular language      3
Regular language in       155
Regular language, defined with nonregular numerical predicates      164
Regular numerical predicate      25—28
Relativization      81 105 117
S1S      34
Second-order formula      10
Semidirect product      61—65
Semidirect product, bilateral      62
Semidirect product, unilateral      62
Semigroup      6
Semigroup, cyclic      180
Semigroup, free      7
Semigroup, left-simple      180
Semigroup, left-zero      181
Semigroup, transformation      183
Sentence      13

О проекте