Last update:
Wed Sep 26 08:25:13 MDT 2018
A. Schonhage A lower bound for the length of addition
chains . . . . . . . . . . . . . . . . . 1--12
M. S. Paterson Complexity of monotone networks for
Boolean matrix product . . . . . . . . . 13--20
V. Strassen The computational complexity of symbolic
differentiation of interpolating
polynomials . . . . . . . . . . . . . . 21--25
G. P. Huet A unification algorithm for typed
$\lambda$-calculus . . . . . . . . . . . 27--57
A. Ehrenfeucht and
K. P. Lee and
G. Rozenberg Subword complexities of various classes
of deterministic developmental languages
without interactions . . . . . . . . . . 59--75
A. Reedy and
W. J. Savitch The Turing degree of the inherent
ambiguity problem for context-free
languages . . . . . . . . . . . . . . . 77--91
A. Restivo A combinatorial property of codes having
finite synchronization delay . . . . . . 95--101
R. E. Ladner and
N. A. Lynch and
A. L. Selman A comparison of polynomial time
reducibilities . . . . . . . . . . . . . 103--123
G. D. Plotkin Call-by-name, call-by-value and the
lambda-calculus . . . . . . . . . . . . 125--159
L. H. Harper and
W. N. Hsieh and
J. E. Savage A class of Boolean functions with linear
combinational complexity . . . . . . . . 161--133
F. P. Preparata A fast stable sorting algorithm with
absolutely minimum storage . . . . . . . 185--190
R. Moll An operator embedding theorem for
complexity classes of recursive
functions . . . . . . . . . . . . . . . 193--198
J. Leeuwen and
D. Wood A decomposition theorem for
hyper-algebraic extensions of language
families . . . . . . . . . . . . . . . . 199--214
R. V. Book Translational lemmas, polynomial time,
and $(\log n)^j$ --- space . . . . . . . 215--216
M. Mignotte Algorithms relating to the decomposition
of polynomials . . . . . . . . . . . . . 227--235
M. R. Garey and
D. S. Johnson Some simplified NP-complete graph
problems . . . . . . . . . . . . . . . . 237--267
S. A. Greibach Remarks on the complexity of
nondeterministic counter languages . . . 269--288
C. P. Schnorr The combinational complexity of
equivalence . . . . . . . . . . . . . . 289--295
E. P. Friedman The inclusion problem for simple
languages . . . . . . . . . . . . . . . 297--316
J. Karhumaki Two theorems concerning recognizable
N-subsets of sigma * . . . . . . . . . . 317--323
A. Ehrenfeucht and
G. Rozenberg and
S. Skyum A relationship between ET0L and EDT0L
languages . . . . . . . . . . . . . . . 325--330
W. Marek and
Z. Pawlak Information storage and retrieval
systems: mathematical foundations . . . 331--354
M. L. Fredman How good is the information theory bound
in sorting? . . . . . . . . . . . . . . 355--361
I. Meznik On some subclasses of the class of
generable languages . . . . . . . . . . 1--7
J. Engelfriet Surface tree languages and parallel
derivation trees . . . . . . . . . . . . 9--27
S. Ginsburg and
J. Goldstine and
S. Greibach Some uniformly erasable families of
languages . . . . . . . . . . . . . . . 29--44
G. J. Chaitin Information-theoretic characterizations
of recursive infinite strings . . . . . 45--48
P. M. B. Vitanyi Deterministic Lindenmayer languages,
nonterminals and homomorphisms . . . . . 49--71
M. Machtey Minimal pairs of polynomial degrees with
subexponential complexity . . . . . . . 73--76
M. Hack The quality problem for vector addition
systems is undecidable . . . . . . . . . 77--95
J.-J. Levy An algebraic interpretation of the
lambda beta K-calculus; and an
application of a labelled
lambda-calculus . . . . . . . . . . . . 97--114
G. T. Herman and
A. Walker On the stability of some biological
schemes with cellular interactions . . . 115--130
H. Egli and
R. L. Constable Computability concepts for programming
language semantics . . . . . . . . . . . 133--145
J. I. Seiferas and
R. McNaughton Regularity-preserving relations . . . . 147--154
J. W. De Bakker Least fixed points revisited . . . . . . 155--181
B. K. Rosen Correctness of parallel programs: the
Church--Rosser approach . . . . . . . . 183--207
L. Boasson Algebraic languages, iterative pairs and
rational transductions . . . . . . . . . 209--223
M. B. Trakhtenbrot Relationships between classes of
monotonic functions . . . . . . . . . . 228--247
B. Vilfan Lower bounds for the size of expressions
for certain functions in $d$-ary logic 249--269
O. H. Ibarra and
S. K. Sahni and
C. E. Kim Finite automata with multiplication . . 271--294
F. N. Springsteel On the pre-AFL of (log n) space and
related families of languages . . . . . 295--304
C. P. Schnorr A lower bound on the number of additions
in monotone computations . . . . . . . . 305--315
M. Soittola Positive rational sequences . . . . . . 317--322
M. Dezani-Ciancaglini Characterization of normal forms
possessing inverse in the
$\lambda-\beta-\eta$-calculus . . . . . 323--337
S. Even and
R. E. Tarjan Computing an $st$-numbering . . . . . . 339--344
E. Minicozzi Some natural properties of
strong-identification in inductive
inference . . . . . . . . . . . . . . . 345--360
H. B. Hunt and
D. J. Rosenkrantz and
T. G. Szymanski The covering problem for linear
context-free grammars . . . . . . . . . 361--382
W. J. Paul Realizing Boolean functions on disjoint
sets of variables . . . . . . . . . . . 383--396
M. S. Paterson and
L. G. Valiant Circuit size is nonlinear in depth . . . 397--400
L. J. Stockmeyer The polynomial-time hierarchy . . . . . 1--22
C. Wrathall Complete sets and the polynomial-time
hierarchy . . . . . . . . . . . . . . . 23--33
G. Lallement Regular semigroups with D=R as syntactic
monoids of prefix codes . . . . . . . . 35--49
G. Hotz Conditions for balanced trees on
weighted distributions . . . . . . . . . 51--59
B. Monien A recursive and a grammatical
characterization of the exponential-time
languages . . . . . . . . . . . . . . . 61--74
K. Culik, II On the decidability of the sequence
equivalence problem for D0L-systems . . 75--84
T. Araki and
T. Kasami Some decision problems related to the
reachability problem for Petri nets . . 85--104
N. D. Jones and
W. T. Laaser Complete problems for deterministic
polynomial time . . . . . . . . . . . . 105--117
D. C. Jensen and
T. Pietrzykowski Mechanizing omega-order type theory
through unification . . . . . . . . . . 123--171
D. Park Finiteness is mu-ineffable . . . . . . . 173--181
W. Lipski, Jr. Information storage and
retrieval-mathematical foundations II.
Combinatorial problems . . . . . . . . . 183--211
J. Hartmanis and
L. Berman On tape bounds for single letter
alphabet language processing . . . . . . 213--224
H. Barendregt A global representation of the recursive
functions in the $\lambda$-calculus . . 225--242
M. P. Schutzenberger On the rational relations between free
monoids . . . . . . . . . . . . . . . . 243--259
P. H. Starke Analysis and synthesis of asynchronous
ND-automata . . . . . . . . . . . . . . 261--266
A. Schonhage An elementary proof for Strassen's
degree bound . . . . . . . . . . . . . . 267--272
T. G. Szymanski Concerning bounded-right-context
grammars . . . . . . . . . . . . . . . . 273--282
K. Ruohonen Zeros of Z-rational functions and D0L
equivalence . . . . . . . . . . . . . . 283--292
A. K. Chandra and
D. S. Hirschberg and
C. K. Wong Approximate algorithms for some
generalized knapsack problems . . . . . 293--304
C. Beeri An improvement on Valiant's decision
procedure for equivalence of
deterministic finite turn pushdown
machines . . . . . . . . . . . . . . . . 305--320
D. E. Knuth and
L. T. Pardo Analysis of a simple factorization
algorithm . . . . . . . . . . . . . . . 321--348
R. J. Lipton and
D. Dobkin Complexity measures and hierarchies for
the evaluation of integers and
polynomials . . . . . . . . . . . . . . 349--357
D. S. Wise A strong pumping lemma for context-free
languages . . . . . . . . . . . . . . . 359--369
R. L. Rivest and
J. Vuillemin On recognizing graph properties from
adjacency matrices . . . . . . . . . . . 371--384
R. Milner Fully abstract models of typed
$\lambda$-calculi . . . . . . . . . . . 1--22
Z. Galil On the complexity of regular resolution
and the Davis--Putnam procedure . . . . 23--46
H. P. Schutzenberger On a variant of sequential functions . . 47--57
D. J. Lehmann Algebraic structures for transitive
closure . . . . . . . . . . . . . . . . 59--76
J. Vuillemin How to verify the connectivity of a
group table . . . . . . . . . . . . . . 77--82
M. Linna A decidability result for deterministic
omega-context-free languages . . . . . . 83--98
T. Araki and
T. Kasami Decidable problems on the strong
connectivity of Petri net reachability
sets . . . . . . . . . . . . . . . . . . 99--119
G. Markowsky Categories of chain-complete posets . . 125--135
C. Hosono and
M. Sato The retracts in P omega do not form a
continuous lattice --- a solution to
Scott's problem . . . . . . . . . . . . 137--142
M. M. Geller and
H. B. Hunt, III and
T. G. Szymanski and
J. D. Ullman Economy of description by parsers,
DPDA's, and PDA's . . . . . . . . . . . 143--153
J. Francon On the analysis of algorithms for trees 155--169
H.-G. Stork On the paging-complexity of periodic
arrangements . . . . . . . . . . . . . . 171--197
H. Maurer and
Th. Ottmann and
A. Salomaa On the form equivalence of L-forms . . . 199--225
J. Ferrante and
J. R. Geiser An efficient decision procedure for the
theory of rational order . . . . . . . . 227--233
D. J. Lehmann A note on Schnorr's separatedness . . . 235
C. H. Papadimitriou The Euclidean traveling salesman problem
is NP-complete . . . . . . . . . . . . . 237--244
M. M. Geller and
M. A. Harrison On LR(k) grammars and languages . . . . 245--276
N. D. Jones and
L. H. Landweber and
Y. E. Lien Complexity of some problems in Petri
nets . . . . . . . . . . . . . . . . . . 277--299
R. Daley On the inference of optimal descriptions 301--319
T. Olshansky and
A. Pnueli A direct algorithm for checking
equivalence of LL(k) grammars . . . . . 321--349
W. A. Burkhard Non-uniform partial-match file designs 1--23
Y. S. Kwong On reduction of asynchronous systems . . 25--50
L. Chottin Syntactical study of certain language
solutions of operator equations . . . . 51--84
J. Engelfriet Iterating iterated substitution . . . . 85--100
A. Mandel and
I. Simon On finite semigroups of matrices . . . . 101--111
A. B. Cremers and
T. N. Hibbard On the formal definition of dependencies
between the control and information
structure of a data space . . . . . . . 113--128
M. Latteux Product in the rational cone produced by
D/sub 1/* . . . . . . . . . . . . . . . 129--134
L. Aiello and
M. Aiello and
R. W. Weyhrauch PASCAL in LCF: semantics and examples of
proof . . . . . . . . . . . . . . . . . 135--177
Z. Galil and
N. Megiddo Cyclic ordering is NP-complete . . . . . 179--182
G. Jacob An algorithm for calculating the
cardinal, finite or infinite, of the
semigroups of matrices . . . . . . . . . 183--204
M. D. Atkinson The complexity of group algebra
computations . . . . . . . . . . . . . . 205--209
J. Karhumaki Remarks on commutative $N$-rational
series . . . . . . . . . . . . . . . . . 211--217
C. Reutenauer On a question of S. Eilenberg (rational
sequences) . . . . . . . . . . . . . . . 219
G. D. Plotkin LCF considered as a programming language 223--255
M. B. Smyth Effectively given domains . . . . . . . 257--274
C. C. Elgot and
L. Snyder On the many facets of lists . . . . . . 275--305
S. Ginsburg and
E. H. Spanier Pushdown acceptor forms . . . . . . . . 307--320
H. Luckhardt A fundamental effect in computations on
real numbers . . . . . . . . . . . . . . 321--324
C. Choffrut Rational relations characterization of
sequential and subsequential functions 325--337
G. Rozenberg and
M. Penttonen and
A. Salomaa Bibliography of L systems . . . . . . . 339--354
R. S. Cohen and
A. Y. Gold Omega-computations on Turing machines 1--23
N. Lynch Log space machines with multiple oracle
tapes . . . . . . . . . . . . . . . . . 25--39
H. Abelson Towards a theory of local and global in
computation . . . . . . . . . . . . . . 41--67
K. Culik, II and
H. A. Maurer and
Th. Ottmann On two-symbol complete E0L Forms . . . . 69--92
D. S. Johnson and
F. P. Preparata The densest hemisphere problem . . . . . 93--107
Z. Manna and
A. Shamir The convergence of functions to fixed
points of recursive definitions . . . . 109--141
K. Culik, II and
H. A. Maurer and
Th. Ottmann and
K. Ruohonen and
A. Salomaa Isomorphism, form equivalence and
sequence equivalence of DP0L forms . . . 143--173
S. A. Greibach One way finite visit automata . . . . . 175--221
C. Rackoff The covering and boundedness problems
for vector addition systems . . . . . . 223--231
V. L. Bennison and
R. I. Soare Some lowness properties and
computational complexity sequences . . . 233--254
B. Courcelle A representation of trees by languages.
I . . . . . . . . . . . . . . . . . . . 255--279
D. E. Knuth and
A. Schonhage The expected linearity of a simple
equivalence algorithm . . . . . . . . . 281--315
D. Bollman and
M. Laplaza Some decision problems for polynomial
mappings . . . . . . . . . . . . . . . . 317--325
A. Ehrenfeucht and
G. Rozenberg E0L languages are not codings or FP0L
languages . . . . . . . . . . . . . . . 327--341
H. F. de Groote On varieties of optimal algorithms for
the computation of bilinear mappings. I.
The isotropy group of a bilinear mapping 1--24
B. Courcelle A representation of trees by languages.
II . . . . . . . . . . . . . . . . . . . 25--55
J. B. Wright and
E. G. Wagner and
J. W. Thatcher A uniform approach to inductive posets
and inductive closure . . . . . . . . . 57--77
P. van Emde Boas Some applications of the McCreight-Meyer
algorithm in abstract complexity theory 79--98
R. Verbeek and
K. Weihrauch Data representation and computational
complexity . . . . . . . . . . . . . . . 99--116
M. Mignotte Intersection of images of certain
recurrent linear series . . . . . . . . 117--121
H. F. de Groote On varieties of optimal algorithms for
the computation of bilinear mappings.
II. Optimal algorithms for 2*2-matrix
multiplication . . . . . . . . . . . . . 127--148
K. Kobayashi On the minimal firing time of the firing
squad synchronization problem for
polyautomata networks . . . . . . . . . 149--167
A. Ehrenfeucht and
G. Rozenberg Elementary homomorphisms and a solution
of the D0L sequence equivalence problem 169--183
R. V. Book and
C. Wrathall On languages specified by relative
acceptance . . . . . . . . . . . . . . . 185--195
J.-F. Perrot Varieties of languages and operations 197--210
J. E. Pin On the syntactic monoid of L* where L is
a finite language . . . . . . . . . . . 211--215
D. E. Muller and
F. P. Preparata Finding the intersection of two convex
polyhedra . . . . . . . . . . . . . . . 217--236
H. F. de Groote On varieties of optimal algorithms for
the computation of bilinear mappings.
III. Optimal algorithms for the
computation of $xy$ and $yx$ where $x,y$
in $M_2(K)$ . . . . . . . . . . . . . . 239--249
C. P. Schnorr Improved lower bounds on the number of
multiplications/divisions which are
necessary to evaluate polynomials . . . 251--261
S. Skyum On good ET0L forms . . . . . . . . . . . 263--272
J. Hartmanis On log-tape isomorphisms of complete
sets . . . . . . . . . . . . . . . . . . 273--286
O. H. Ibarra On two-way sequential transductions of
full semi-AFLs . . . . . . . . . . . . . 287--309
S. A. Greibach Remarks on blind and partially blind
one-way multicounter machines . . . . . 311--324
M. Kleiman and
N. Pippenger An explicit construction of short
monotone formulae for the monotone
symmetric functions . . . . . . . . . . 325--332
E. P. Friedman A note on non-singular deterministic
pushdown automata . . . . . . . . . . . 333--339
E. Soisalon-Soininen On the covering problem for
left-recursive grammars . . . . . . . . 1--11
M. Wand Fixed-point constructions in
order-enriched categories . . . . . . . 13--30
W. Bibel Tautology testing with a generalised
matrix reduction method . . . . . . . . 31--44
F. P. Preparata and
D. E. Muller Finding the intersection of n
half-spaces in time O(n log n) . . . . . 45--55
P. Johansen The generating function of the number of
subpatterns of a D0L sequence . . . . . 57--68
K. Hashiguchi A decision procedure for the order of
regular events . . . . . . . . . . . . . 69--72
K. R. Apt and
J. A. Bergstra and
L. G. L. T. Meertens Recursive assertions are not enough-or
are they? . . . . . . . . . . . . . . . 73--87
M. E. Majster Data types, abstract data types and
their specification problem . . . . . . 89--127
J. Hopcroft and
J.-J. Pansiot On the reachability problem for
$5$-dimensional vector addition systems 135--159
H. Prodinger and
F. J. Urbanek Language operators related to Init . . . 161--175
T. P. Baker and
A. L. Selman A second step toward the polynomial
hierarchy . . . . . . . . . . . . . . . 177--187
L. G. Valiant The complexity of computing the
permanent . . . . . . . . . . . . . . . 189--201
P. Pudlak and
F. N. Springsteel Complexity in mechanized hypothesis
formation . . . . . . . . . . . . . . . 203--225
P. Hajek Arithmetical hierarchy and complexity of
computation . . . . . . . . . . . . . . 227--237
J. Hartmanis Relations between diagonalization, proof
systems, and complexity gaps . . . . . . 239--253
J. Morgenstern An extension of Winograd's theorem . . . 255--259
A. Arnold and
M. Latteux A new proof of two theorems about
rational transductions . . . . . . . . . 261--263
C. Bohm and
M. Dezani-Ciancaglini and
P. Peretti and
S. R. D. Rocca A discrimination algorithm inside
$\lambda$-$\beta$-calculus . . . . . . . 271--291
J. Beauquier Algebraic generation and systems of
iterative pairs . . . . . . . . . . . . 293--323
C. C. Elgot and
J. C. Shepherdson A semantically meaningful
characterization of reducible flowchart
schemes . . . . . . . . . . . . . . . . 325--357
S. Winograd On multiplication in algebraic extension
fields . . . . . . . . . . . . . . . . . 359--377
D. Dolev Commutation properties and generating
sets characterize slices of various
synchronization primitives . . . . . . . 379--391
R. Hindley The discrimination theorem holds for
combinatory weak reduction . . . . . . . 393--394
J.-M. Autebert A note on the cylinder of deterministic
languages . . . . . . . . . . . . . . . 395--399
D. A. Plaisted Fast verification, testing, and
generation of large primes . . . . . . . 1--16
J.-P. Duval Relationship between global periodicity
and repetitions of words . . . . . . . . 17--26
J. Bergstra and
J. W. Klop Church--Rosser strategies in the lambda
calculus . . . . . . . . . . . . . . . . 27--38
I. Guessarian Program transformations and algebraic
semantics . . . . . . . . . . . . . . . 39--65
R. Statman Intuitionistic propositional logic is
polynomial-space complete . . . . . . . 67--72
R. Statman The typed $\lambda$-calculus is not
elementary recursive . . . . . . . . . . 73--81
I. Wegener Switching functions whose monotone
complexity is nearly quadratic . . . . . 83--97
P. Flajolet and
J. C. Raoult and
J. Vuillemin The number of registers required for
evaluating arithmetic expressions . . . 99--125
G. Wechsung and
A. Brandstadt A relation between space, return and
dual return complexities . . . . . . . . 127--140
G. Christol Almost $k$-recognisable periodic sets 141--145
I. Wegener A counterexample to a conjecture of
Schnorr referring to monotone networks 147--150
A. Tang Chain properties in P omega . . . . . . 153--172
M. A. Harrison and
I. M. Havel and
A. Yehudai On equivalence of grammars through
transformation trees . . . . . . . . . . 173--205
J. Karhumaki On commutative DT0L systems . . . . . . 207--220
D. Perrin The ergodic representation of finite
automata . . . . . . . . . . . . . . . . 221--241
E. A. Ashcroft and
F. E. Fich A generalized setting for fixpoint
theory . . . . . . . . . . . . . . . . . 243--256
S. L. Bloom and
R. Tendell Algebraic and graph theoretic
characterizations of structured
flowchart schemes . . . . . . . . . . . 265--286
A. Nijholt Simple chain grammars and languages . . 287--309
K. Inoue and
I. Takanami and
A. Nakamura and
T. Ae One-way simple multihead finite automata 311--328
R. Aubin Mechanizing structural induction. I.
Formal system . . . . . . . . . . . . . 329--346
R. Aubin Mechanizing structural induction. II.
Strategies . . . . . . . . . . . . . . . 347--362
C. Reutenauer On the associated series to certain
Lindenmayer systems . . . . . . . . . . 363--375
K. Ruohonen On some decidability problems for HD0L
systems with nonsingular Parikh matrices 377--384
F. Rodriguez Families of closed languages by open
brackets . . . . . . . . . . . . . . . . 385--398