Last update: Sun Apr 22 02:03:34 MDT 2018
Top |
Symbols |
Numbers |
Math |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
N |
O |
P |
Q |
R |
S |
T |
U |
V |
W |
X |
Y |
Z
BibTeX entry
@Article{Harrow:1978:HSS,
author = "Keith Harrow",
title = "How to show something is not: Proofs in formal
language and computability theory",
journal = j-SIGCSE,
volume = "10",
number = "3",
pages = "27--30",
month = aug,
year = "1978",
CODEN = "SIGSD3",
DOI = "https://doi.org/10.1145/953028.804227",
ISSN = "0097-8418 (print), 2331-3927 (electronic)",
ISSN-L = "0097-8418",
bibdate = "Sun Nov 18 07:38:06 MST 2012",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/sigcse1970.bib",
note = "Proceedings of the 9th SIGCSE symposium on Computer
science education.",
abstract = "Most introductory courses in theoretical computer
science (formal language theory or computability
theory) start with a seemingly endless series of
definitions, including what it means for a grammar or
language to be regular, context-free, etc., or what it
means for a function to be recursive, primitive
recursive, or partial recursive. Bright students
immediately ask two questions. First, what are examples
of languages or functions that belong to one class but
not the other? Second, is some particular language
context-free, or is a particular function recursive? We
must develop new techniques which allow us to give a
negative answer to question two (and thus to answer
question one as well). In this note we will discuss
some of the methods that are often used in elementary
proofs in formal language theory and computability
theory.",
acknowledgement = ack-nhfb,
fjournal = "SIGCSE Bulletin (ACM Special Interest Group on
Computer Science Education)",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J688",
}
Related entries
- allow,
5(1)9,
5(1)26,
5(1)166,
6(1)33,
6(1)46,
7(1)23,
7(4)47,
8(1)113,
8(1)289,
8(1)382,
8(1)389,
8(3)4,
8(3)102,
9(1)26,
9(1)37,
9(1)85,
9(1)145,
9(3)1,
9(3)34,
9(3)43,
9(4)88,
10(1)7,
10(1)80,
10(1)86,
10(1)282,
11(1)54
- answer,
5(1)68,
8(1)100,
8(1)104,
8(1)284,
8(3)4,
9(3)59,
10(3)59,
10(3)67
- ask,
6(1)165,
6(1)169,
10(3)59,
11(1)54
- belong,
7(2)55,
9(3)66
- class,
5(1)177,
5(1)181,
6(1)6,
6(1)133,
6(1)174,
7(1)31,
7(1)86,
7(1)109,
8(1)150,
8(1)179,
8(1)212,
8(3)67,
8(3)143,
9(1)113,
9(1)154,
9(3)16,
9(3)51,
9(3)66,
9(3)74,
9(3)79,
10(1)34,
10(1)53,
10(1)86,
10(1)189,
10(1)260,
10(1)282,
10(3)23,
10(3)45,
10(3)63,
10(4)28,
11(1)23,
11(1)113
- computability,
6(1)37
- context-free,
7(1)191
- definition,
6(1)165,
9(1)175,
9(3)51,
10(1)53,
11(1)228,
11(1)232
- develop,
5(1)26,
5(1)41,
5(1)86,
5(2)33,
7(1)47,
7(1)123,
7(1)148,
7(3)30,
7(3)77,
7(4)25,
8(1)350,
9(1)88,
9(1)175,
9(1)180,
9(1)184,
9(3)6,
9(3)10,
10(1)193,
10(4)28,
11(1)23,
11(1)105,
11(1)215
- discuss,
3(1)12,
3(4)19,
5(1)15,
5(1)56,
5(1)60,
5(1)77,
5(1)106,
6(1)11,
6(1)81,
6(1)90,
6(1)165,
7(1)47,
7(1)51,
7(1)79,
7(1)212,
8(1)62,
8(1)95,
8(1)131,
8(1)200,
8(1)247,
8(1)260,
8(1)266,
8(1)284,
8(1)313,
8(1)372,
8(3)1,
8(3)30,
8(3)184,
9(1)93,
9(1)113,
9(1)123,
9(1)184,
9(3)39,
9(3)51,
9(3)59,
10(1)70,
10(1)183,
10(1)224,
10(1)282,
10(2)12,
10(2)63,
10(3)23,
10(3)31,
10(3)100,
10(3)131,
11(1)6,
11(1)18,
11(1)49,
11(1)140,
11(1)149,
11(1)236
- elementary,
2(3)118,
4(1)110,
6(1)59,
6(1)74,
7(3)38,
8(1)1,
8(1)24,
8(1)393,
8(3)57,
9(1)100,
9(1)142,
9(1)168,
9(3)30,
10(1)183,
10(1)266,
10(3)73,
10(4)20,
11(1)89,
11(1)167
- etc,
4(4)45,
5(1)1,
5(1)24,
5(1)51,
5(2)33,
7(4)25,
8(1)11,
8(1)189,
8(1)253,
8(3)39,
9(1)119,
9(3)66,
10(3)55,
10(3)120
- example,
3(3)19,
3(4)24,
4(1)75,
4(2)10,
6(1)6,
6(1)90,
6(1)133,
7(1)7,
7(1)40,
7(1)47,
7(1)51,
7(1)76,
7(1)102,
7(1)206,
7(3)35,
7(3)58,
8(1)149,
8(1)179,
8(1)260,
8(1)275,
8(1)372,
8(2)45,
8(3)54,
8(3)67,
8(3)78,
8(3)106,
8(3)115,
8(3)143,
9(1)26,
9(1)69,
9(1)108,
9(1)129,
9(1)139,
9(1)151,
9(3)51,
9(3)59,
9(3)79,
10(1)7,
10(1)97,
10(3)108,
10(3)131,
10(4)28,
11(1)162,
11(1)168,
11(1)232
- formal,
2(3)34,
5(1)18,
5(2)33,
6(1)47,
6(1)106,
6(1)148,
7(1)40,
7(1)56,
8(1)280,
8(3)89,
9(3)16,
9(3)51,
10(3)16,
10(3)50,
10(3)63,
10(3)156,
11(1)49,
11(1)131
- free, context-,
7(1)191
- function,
4(1)110,
7(1)31,
7(1)157,
8(1)116,
8(1)131,
8(1)359,
9(1)69,
9(1)133,
9(1)168,
9(2)17,
10(3)162,
11(1)232,
11(1)240
- give,
3(4)24,
5(1)26,
5(1)53,
5(1)149,
5(1)153,
6(1)129,
6(1)152,
7(1)20,
8(1)39,
8(1)192,
8(1)212,
8(1)223,
8(1)295,
8(4)6,
9(1)13,
9(1)139,
9(1)142,
9(3)56,
9(3)59,
9(4)19,
10(1)31,
10(3)55,
10(3)126,
11(1)192
- grammar,
7(1)191,
10(1)179
- how,
3(1)21,
3(4)24,
4(1)8,
5(1)91,
6(1)28,
6(1)40,
6(1)81,
6(1)169,
7(1)51,
7(1)56,
7(1)102,
7(1)123,
7(1)133,
7(1)191,
7(3)30,
7(3)77,
8(1)17,
8(1)35,
8(1)79,
8(1)90,
8(1)223,
8(1)236,
8(1)253,
8(1)289,
8(1)393,
8(2)11,
8(3)22,
8(3)39,
8(3)129,
9(1)6,
9(1)26,
9(1)53,
9(1)88,
9(1)108,
9(1)119,
9(1)123,
9(1)129,
9(1)133,
9(1)145,
9(1)165,
9(1)173,
9(1)180,
9(3)1,
9(3)21,
10(1)33,
10(1)34,
10(1)36,
10(1)53,
10(1)65,
10(1)177,
10(1)178,
10(3)31,
10(3)59,
10(3)67,
10(3)136,
11(1)14,
11(1)23,
11(1)49,
11(1)149,
11(1)232,
11(2)52
- immediately,
6(1)184,
10(1)282,
10(3)55,
11(4)31
- including,
5(1)1,
5(1)2,
5(1)15,
5(1)68,
5(1)77,
6(1)133,
7(1)83,
7(2)21,
7(2)33,
7(2)67,
8(1)39,
8(1)150,
8(1)167,
8(1)266,
8(2)36,
8(3)12,
8(3)102,
9(1)59,
9(1)88,
9(1)142,
9(1)173,
9(3)74,
10(1)53,
10(1)282,
10(3)50,
10(3)67,
10(3)93,
10(3)113
- mean,
4(1)75,
5(1)26,
5(1)83,
5(1)91,
5(1)125,
5(1)149,
6(1)165,
6(1)184,
6(4)26,
7(1)47,
7(1)68,
7(1)79,
7(1)114,
7(1)124,
7(1)196,
7(2)33,
8(1)158,
8(1)179,
8(1)275,
8(1)393,
9(1)26,
10(1)97,
10(1)178,
10(1)193,
10(4)20,
11(1)79,
11(1)149
- method,
5(1)1,
5(1)6,
5(1)51,
5(1)83,
6(1)37,
6(1)47,
6(1)48,
6(1)97,
6(1)101,
6(1)184,
6(4)21,
7(1)31,
7(1)83,
7(1)129,
7(1)172,
7(2)87,
8(1)1,
8(1)49,
8(1)84,
8(1)179,
8(1)189,
8(1)200,
8(1)212,
8(1)266,
8(3)30,
8(3)108,
8(4)15,
9(1)168,
9(3)10,
9(3)28,
9(3)39,
9(3)51,
9(3)59,
9(3)66,
9(3)74,
10(1)33,
10(1)86,
10(1)178,
10(1)189,
10(1)224,
10(1)266,
10(3)8,
10(4)30,
11(1)41,
11(1)89,
11(1)127,
11(1)162,
11(1)247,
11(2)23
- most,
3(1)21,
3(4)24,
4(1)75,
4(1)160,
4(2)10,
5(1)6,
5(1)21,
5(1)38,
5(1)60,
5(1)70,
5(1)91,
5(1)119,
5(1)125,
5(1)149,
5(1)157,
6(1)1,
6(1)6,
6(1)33,
6(1)46,
6(1)79,
6(1)81,
6(1)90,
6(1)106,
6(1)165,
6(1)184,
6(4)26,
7(1)7,
7(1)20,
7(1)51,
7(1)83,
7(1)109,
7(1)172,
8(1)11,
8(1)39,
8(1)69,
8(1)100,
8(1)113,
8(1)192,
8(1)247,
8(3)39,
9(1)31,
9(1)88,
9(1)96,
9(1)100,
9(1)113,
9(1)139,
9(1)145,
9(1)151,
9(3)16,
10(1)70,
10(1)86,
10(1)96,
10(1)119,
10(1)132,
10(1)183,
10(1)255,
10(3)31,
10(3)35,
10(3)45,
10(3)63,
10(3)67,
10(3)80,
10(3)84,
10(3)131,
10(3)136,
10(3)156,
10(4)28,
10(4)66,
11(1)6,
11(1)87,
11(1)101,
11(1)168,
11(1)202,
11(1)224
- must,
3(4)24,
4(2)10,
5(1)21,
5(1)83,
5(1)97,
5(1)102,
5(1)181,
5(2)33,
6(1)1,
6(1)6,
6(1)21,
6(1)46,
6(1)81,
7(1)109,
7(1)123,
7(1)143,
7(1)200,
7(3)30,
7(3)77,
7(4)25,
8(1)29,
8(1)35,
8(1)69,
8(1)86,
8(1)260,
8(1)284,
8(3)30,
8(3)57,
9(1)88,
9(1)180,
10(1)86,
10(1)92,
10(1)96,
10(1)97,
10(1)178,
10(1)179,
10(1)255,
10(3)55,
10(3)84,
10(3)120,
10(3)162,
11(1)49,
11(1)192
- negative,
3(4)24,
5(1)145,
5(1)173,
7(2)87
- new,
2(3)61,
2(3)118,
2(4)41,
2(5)43,
3(1)10,
4(1)8,
4(1)75,
4(1)160,
5(1)24,
5(1)41,
5(1)60,
5(1)77,
5(1)86,
5(1)134,
5(1)173,
6(1)1,
6(1)15,
6(1)21,
6(1)46,
6(1)48,
6(1)79,
6(1)129,
6(2)24,
6(3)91,
7(1)7,
7(1)65,
7(1)68,
7(1)83,
7(1)179,
7(2)21,
7(4)25,
8(1)11,
8(1)158,
8(1)179,
8(1)192,
8(1)247,
8(1)350,
8(1)359,
8(3)67,
8(3)92,
8(3)125,
8(4)6,
9(1)1,
9(1)123,
9(1)133,
9(1)180,
9(3)1,
9(3)6,
9(4)63,
10(1)32,
10(1)80,
10(1)189,
10(3)67,
10(3)162,
11(1)6,
11(1)22,
11(1)23,
11(1)49,
11(1)61,
11(1)70,
11(1)82,
11(1)87,
11(1)167,
11(3)9,
11(4)25
- note,
2(3)118,
3(1)12,
3(3)15,
5(1)32,
6(1)81,
6(2)1,
6(4)1,
7(2)1,
7(4)44,
9(4)45,
9(4)57,
10(1)79,
10(2)34,
10(3)59,
10(3)80
- often,
3(4)24,
5(1)53,
5(1)134,
5(1)181,
6(1)184,
7(1)11,
7(1)15,
7(1)40,
8(1)17,
8(1)90,
8(1)100,
8(1)116,
8(1)260,
8(1)268,
8(1)295,
8(1)335,
8(3)54,
8(3)125,
9(1)85,
9(1)96,
9(1)154,
9(1)168,
9(3)1,
9(3)51,
9(3)59,
10(1)86,
10(1)97,
10(1)224,
11(1)70,
11(1)79
- partial,
6(1)40,
8(1)24,
8(3)61,
9(1)53,
9(3)59,
9(3)63,
11(1)105
- particular,
2(3)61,
3(4)24,
5(1)9,
5(1)24,
5(1)91,
5(1)181,
5(2)33,
6(1)15,
6(1)59,
6(4)26,
7(1)20,
7(1)40,
7(1)168,
7(3)38,
8(1)49,
8(1)137,
8(1)200,
8(1)289,
8(1)298,
8(1)350,
8(3)75,
9(1)6,
9(1)100,
9(1)123,
9(1)168,
9(1)180,
10(1)87,
10(3)55,
10(3)67,
10(4)66,
11(1)155,
11(1)158
- primitive,
7(1)20,
8(1)393,
8(3)108
- proof,
6(1)90,
7(1)83,
8(1)280,
9(1)142
- question,
2(4)30,
2(4)41,
2(5)43,
3(4)24,
5(1)70,
6(1)6,
6(1)97,
7(1)31,
7(1)109,
8(1)86,
8(1)104,
8(1)275,
8(1)289,
8(1)371,
8(3)4,
8(3)26,
8(3)92,
8(3)94,
9(1)108,
9(1)133,
9(3)16,
9(3)59,
9(3)66,
10(1)119,
10(3)67,
10(3)136,
11(1)87,
11(1)140
- recursive,
4(1)110,
8(1)17,
8(1)116,
8(3)30,
9(1)129,
9(1)151
- regular,
5(1)2,
5(1)110,
7(1)68,
7(1)196,
10(1)32,
10(3)80
- second,
2(3)118,
4(2)10,
4(2)14,
5(1)70,
5(1)97,
5(1)134,
7(1)95,
8(1)182,
8(1)280,
8(3)95,
9(1)37,
9(1)59,
9(1)88,
9(1)133,
9(3)43,
9(3)79,
10(1)97,
10(3)23,
10(3)45,
10(3)50,
10(3)55,
10(3)100,
10(3)113,
10(3)120,
10(3)136,
11(1)187,
11(1)192,
11(1)215,
11(1)236
- seemingly,
6(1)174
- series,
5(1)173,
6(1)74,
6(3)91,
7(1)124,
8(1)95,
8(1)167,
8(1)372,
8(3)2,
8(3)98,
8(3)143,
9(3)79,
10(3)63,
11(1)89,
11(1)232
- show,
4(2)10,
6(1)111,
7(1)133,
8(1)49,
8(1)192,
8(3)54,
8(3)78,
9(1)108,
11(2)27,
11(2)40
- something,
3(4)24,
5(1)24,
6(1)46,
6(1)165
- start,
6(2)45,
8(1)11,
8(3)54,
9(1)93,
10(1)27,
10(1)96,
11(4)31
- technique,
3(4)24,
4(1)154,
4(4)11,
5(1)9,
5(1)26,
5(1)38,
5(1)119,
5(4)29,
6(1)6,
6(1)47,
6(1)59,
6(1)101,
6(1)184,
6(3)46,
6(4)26,
7(1)23,
7(1)47,
7(1)86,
7(1)123,
7(1)206,
7(2)67,
8(1)11,
8(1)39,
8(1)158,
8(1)179,
8(1)189,
8(1)200,
8(1)268,
8(1)355,
8(3)30,
8(3)67,
8(3)106,
8(3)111,
8(3)135,
8(3)143,
8(4)10,
8(4)15,
8(4)53,
9(1)154,
9(1)168,
9(3)28,
9(3)74,
10(1)33,
10(1)34,
10(1)65,
10(1)80,
10(1)86,
10(1)178,
10(1)180,
10(1)189,
10(1)232,
10(3)55,
10(3)63,
10(3)131,
10(4)42,
11(1)23,
11(1)28,
11(1)54,
11(1)79,
11(1)89,
11(1)192
- theoretical,
3(1)21,
5(1)45,
5(1)91,
5(1)177,
7(1)191,
8(1)223,
8(1)268,
8(2)36,
9(1)108,
10(1)232,
10(2)39,
10(3)136,
11(1)23,
11(1)192
- theory,
2(3)34,
2(3)118,
4(1)110,
5(1)1,
5(1)51,
5(1)83,
5(1)177,
6(1)21,
6(1)33,
6(1)37,
6(1)79,
6(1)148,
6(1)165,
7(1)191,
8(1)116,
8(1)212,
8(1)280,
8(1)284,
8(1)289,
9(1)53,
10(1)7,
10(1)96,
10(1)255,
10(3)55,
11(1)23,
11(1)45,
11(1)182
- thus,
3(4)24,
4(2)10,
5(1)45,
5(1)51,
5(1)153,
5(1)177,
5(2)33,
6(1)74,
7(1)31,
7(1)200,
8(1)289,
8(1)389,
9(1)100,
10(1)7,
10(1)80,
10(1)178,
10(1)266,
10(3)67,
11(1)141,
11(1)167
- well,
2(3)118,
3(4)19,
4(1)110,
4(1)160,
5(1)21,
5(1)38,
5(1)45,
5(1)83,
5(1)138,
5(1)173,
6(1)97,
6(1)161,
7(1)40,
7(1)123,
7(1)133,
7(1)196,
7(3)30,
7(4)25,
7(4)53,
8(1)35,
8(1)90,
8(1)100,
8(1)179,
8(1)192,
8(1)212,
8(1)275,
8(1)280,
8(1)284,
8(2)11,
8(3)54,
9(1)6,
9(1)22,
9(1)53,
9(1)77,
9(1)119,
9(1)180,
9(3)39,
10(1)97,
10(1)179,
10(1)210,
10(3)50,
10(4)20,
11(1)6,
11(1)54,
11(1)61,
11(1)70,
11(1)75,
11(1)131,
11(1)149,
11(1)182,
11(1)202
- what,
2(4)41,
3(4)24,
5(1)6,
5(1)21,
5(1)68,
5(1)177,
6(1)6,
6(1)40,
6(1)46,
6(1)79,
6(1)81,
6(1)125,
6(1)165,
6(1)169,
7(1)7,
7(1)15,
7(1)95,
7(1)109,
7(3)30,
8(1)69,
8(1)79,
8(1)86,
8(1)104,
8(1)137,
8(1)236,
8(1)268,
8(1)304,
8(1)307,
8(1)313,
8(1)335,
9(1)6,
9(1)100,
9(1)119,
9(1)123,
9(1)165,
9(1)168,
9(3)30,
9(3)39,
10(1)31,
10(1)36,
10(1)70,
10(1)96,
10(1)97,
10(1)178,
10(1)266,
10(3)13,
10(3)67,
10(3)131,
10(3)136,
10(4)42,
11(1)6,
11(1)49,
11(1)140,
11(1)167,
11(1)168,
11(1)195