CS 378: Lecture Notes


Copyright © Gordon S. Novak Jr.

Permission is granted for individuals to make copies of these notes for personal use, or for instructors to make copies for classroom use.

Note: Some of these pages use math symbols such as: ∀ ∃ . Microsoft Internet Explorer will not display the math symbols, but Firefox will.

Contents

abstract syntax tree 41, 112

affix 253

alist 33, 93

ambiguity 251, 263

amphion 166

anaphora 252

annotate 122

anonymous function 35

antecedent 216

append 26

assoc 33

association list 33, 93

associative 315

assocl 93

ast 41, 112

astronomical software 166

atn 276

atom 137

atomic 342

augmented transition network 276

automaton 269

available 83

backtrack 70

backward chaining 141, 142, 183

base case 16, 18

bayes theorem 206

bayesian network 210

bigram 257

bijective 312

binary tree recursion 46

binding 9, 93, 116

binding list 93

binding time analysis 122

bottom-up parser 275

bound 150

bounded depth-first search 67

branching factor 70

buffer 333

buffering 333

busy 83

car 12

case frame 254

cdr 12

certainty factor 214

certainty factor combination 219

chaff 148

chain rule 209

child 39

clojure 5

closure 5

cnf 146

combinator 86

combinatoric explosion 52

commutative 315

compile-time 91

compiler generator 123

complete 159

composition 4, 166

compositional semantics 293

conceptual island 239

conditional probability 206

confluence 111

conjunction 137

conjunctive normal form 146

cons 10, 11

consistent 138

constant folding 109

constant propagation 116

context free 271

context-free 260

correctness 110

davis-putnam 148

de morgans laws 139

decision tree 227, 228

deduction 166

definite determiner 283

deftrace 17

denote 3

depth bound 67

depth-first search 54, 65, 70

design pattern 19, 23, 47, 88, 95

determiner 283

dfs 54, 70

disjunction 137

disk access 333

do 37

domain 312

doseq 38

dynamic 116, 122

dynamic data 116

eliza 288, 289, 290

emit 326, 332

empty list 10

empty? 20

emycin 203, 204

entail 159

equal 96

euclidean distance 321

eval 51

every 36

expression tree 40

external notation 8

filter 318, 319

finite automaton 270

first 12, 13

first child next sibling 44

first-order logic 150

first-order predicate calculus 135

fixpoint 107

flatten 48

fn 35

folding 109

fopc 135

for all 36

free 150

functional program 4, 314

futamura projections 123

gensym 113

grammar 260, 268

grammar notation 267

grammatical ambiguity 251, 264

ground literal 140

hidden markov 258

homograph 264

homoiconic 8

horn clause 141, 163

i/o buffer 333

implication 137

in-line 114

inconsistent 138

indefinite determiner 283

inference 134

infinite loop 16

information theory 248

injective 312

inline 114

interior node 39

interpretation 116, 138

intersection 30

invalid 138

isomorphism 316

iterative deepening 68

joint probability distribution 208

jvm 5

knowledge base 134

knowledge representation 132

knowledge retrieval 132

knowledge source 242

knowledge-based strategy 197

knuth-bendix 111

language generation 261

language translation 129

leaf 39

left recursion 295

let 34

lexical ambiguity 251, 264

lexical features 255

lexicon 254

lhs 45

link 10, 39

linked list tree 45

list 10

list recursion 20

list tail recursion 22

literal 146

live 83

load balancing 332, 334

loop unrolling 91

low-pass filter 236

macro 113

map 35, 317

mapcan 318

mapcat 318

mapping 312, 317

mapreduce 322

mapreduce key 325

master 331

match 100, 102

member 29

metonymy 252

mix 116

model 138

model checking 140

modus ponens 139

morphological analyzer 253

morphology 253

n-gram 257

natural deduction 163

natural language 245

negation 137

nested tree recursion 98

non-terminal 260

nonterminal symbol 268

offline 122

one-to-one 312

online 122

onto 312

op 45

open 114

operator 52, 70

operators 53

optimization 108

overfitting 244

pagerank 336

parse tree 42, 262

parsing 112, 262, 273

part of speech 254, 260

partial evaluation 115, 116

pattern matching 100

phrase structure 268

postorder 51

pragmatics 250

precompute 116

predicate 29

predicate calculus 150

prefix 253

println 37

production 260, 268

prolog 185

propositional calculus 135

propositional database 181

propositional logic 137

propositional variable 137

quote 9

range 312

reasoning 132

recall 244

recognizer 269

recognizing automaton 269

recursion 16, 16

recursive case 18

recursive descent 295

recursively enumerable 266

reduce 35, 320

reducing 116

reference 283

referent 3, 284

regular language 270

relaxation 336

representation hypothesis 133

resolution 160, 161, 162

rest 12, 13

reverse 24

rewrite rule 88

rhs 45

robot mouse 60

root 39

root word 253

rule 201

rule induction 229

rule subsumption 223

rule-based system 201

run-time 91

sat 147, 148

sat solver 140

satisfiability 147, 148

search 52, 70

search design pattern 57

semantic grammar 290

semantic marker 254

semantics 250, 252, 293

sensitivity analysis 226

sentence symbol 268

set 29

set difference 32

shard 314

side effect 4

side-effect 314

simulation 316

skolem constant 152

skolem function 152

skolemization 152

solving equations 71

some 36

sort 38

sound 159

specialize 116

splitting 163

start symbol 268

state space 53, 53

states 53

static 116, 122

static data 116

structure sharing 11, 26

sublis 94, 95, 155

subst 89

substitution 94, 155

suffix 253

suffix-stripping 253

surjective 312

symbol 3

syntax 250

tail recursion 23

tail recursive 22

tail-call optimization 23

terminal 260

terminal symbol 268

termination 111

there exists 36

token 257

top-down filtering 274

top-down parser 274

trace 17

training set phenomenon 244

transform 104, 112, 116, 123

transformation 108

transformation rule 104

tree 39

tree nested recursion 48

tree recursion 47, 55

truth table 140

type 257

unfolding 116

unification 153

unigram 257

union 32

unparsing 112

unrolling 91

unsatisfiable 138

valid 138

variable capture 113

vocabulary 268

walksat 148

well-founded ordering 16

when 37

worker 331

zipfs law 249


CS 378