Last update:
Tue Sep 25 19:04:28 MDT 2018
E. G. Wagner Algebras, polynomials and programs . . . 3--34
E. S. Bainbridge and
P. J. Freyd and
A. Scedrov and
P. J. Scott Functorial polymorphism . . . . . . . . 35--64
M. Barr Fixed points in Cartesian closed
categories . . . . . . . . . . . . . . . 65--72
S. L. Bloom A note on guarded theories . . . . . . . 73--83
P. S. Mulry Categorical fixed point semantics . . . 85--97
H. R. Nielson and
F. Nielson Functional completeness of the mixed
$\lambda$-calculus and combinatory logic 99--126
A. Pasztor Recursive programs and denotational
semantics in absolute logics of programs 127--150
C. Bottinger On Scott's thesis for domains of
information and well-quasi-orderings . . 151--158
C. Wells A generalization of the concept of
sketch . . . . . . . . . . . . . . . . . 159--178
J. Tiuryn and
D. B. Benson Fixed points in free process algebras.
II . . . . . . . . . . . . . . . . . . . 179--192
G. Longo and
E. Moggi A category-theoretic characterization of
functional completeness . . . . . . . . 193--211
G. Senizergues A characterisation of deterministic
context-free languages by means of
right-congruences . . . . . . . . . . . 213--232
A. Jung Cartesian closed categories of algebraic
CPOs . . . . . . . . . . . . . . . . . . 233--250
G. Gambosi and
J. Nesetril and
M. Talamo On locally presented posets . . . . . . 251--260
A. Terlutte Cyclic rational transductions and
polynomials of rational functions . . . 261--271
A. Ehrenfeucht and
G. Rozenberg Theory of $2$-structures. I. Clans,
basic subclasses, and morphisms . . . . 277--303
A. Ehrenfeucht and
G. Rozenberg Theory of $2$-structures. II.
Representation through labeled tree
families . . . . . . . . . . . . . . . . 305--342
A. Ehrenfeucht and
G. Rozenberg Primitivity is hereditary for
$2$-structures . . . . . . . . . . . . . 343--358
A. Aggarwal and
A. K. Chandra and
M. Snir Communication complexity of PRAMs . . . 3--28
K. Culik, II New techniques for proving the
decidability of equivalence problems . . 29--45
J. Gruska Synthesis, structure and power of
systolic computations . . . . . . . . . 47--77
J. Hartmanis New developments in structural
complexity theory . . . . . . . . . . . 79--93
C. P. Kruskal and
L. Rudolph and
M. Snir A complexity theory of efficient
parallel algorithms . . . . . . . . . . 95--132
P. S. Thiagarajan Some behavioural aspects of net theory 133--153
W. P. Weijland Semantics for logic programs without
occur check . . . . . . . . . . . . . . 155--174
Anonymous INFORMATIKA 88. 2nd French-Soviet
Workshop on Methods of Compilation and
Program Construction . . . . . . . . . . ??
J.-P. Arcangeli and
C. Pomian Principles of plasma pattern and
alternative structure compilation . . . 177--191
M. Billaud Simple operational and denotational
semantics for Prolog with cut . . . . . 193--208
M. A. Bulyonkov Mixed computation and compilation: new
approaches to old problems . . . . . . . 209--226
D. Galmiche Constructive system for automatic
program synthesis . . . . . . . . . . . 227--239
J. Penjam Computational and attribute models of
formal languages . . . . . . . . . . . . 241--264
V. K. Sabelfeld An algorithm deciding functional
equivalence in a new class of program
schemes . . . . . . . . . . . . . . . . 265--279
G. Senizergues Some decision problems about controlled
rewriting systems . . . . . . . . . . . 281--346
H. Ehrig and
F. Parisi-Presicce and
P. Boehm and
C. Rieckhoff and
C. Dimitrovici and
M. Grosse-Rhode Combining data type and recursive
process specifications using projection
algebras . . . . . . . . . . . . . . . . 347--380
S. Dulucq and
D. Gouyou-Beauchamps On the factors of the Sturmian sequences 381--400
A. Gibbons and
W. Rytter Optimally edge-colouring outerplanar
graphs is in NC . . . . . . . . . . . . 401--411
E. G. Manes A transformational characterization of
if-then-else . . . . . . . . . . . . . . 413--417
M. Chrobak and
T. Szymacha and
A. Krawczyk A data structure useful for finding
Hamiltonian cycles . . . . . . . . . . . 419--424
K. Skandalis Nonrecursiveness of the operations on
real numbers . . . . . . . . . . . . . . 425--429
J. Sakarovitch Foreword . . . . . . . . . . . . . . . . 1
L. Budach Topological invariants of classification
problems . . . . . . . . . . . . . . . . 3--26
K. Hashiguchi Improved limitedness theorems on finite
automata with distance functions . . . . 27--38
A. Carpi and
A. de Luca Non-repetitive words relative to a
rewriting system . . . . . . . . . . . . 39--53
A. Restivo Codes and local constraints . . . . . . 55--64
I. Simon Factorization forests of finite height 65--94
Anonymous CAAP '88 --- 13th Colloque sur les
Arbres en Alg\`ebre et en Programmation.
(French) [Colloquium on Trees in Algebra
and Programming] . . . . . . . . . . . . ??
M. Dauchet and
J. L. Remy Editorial . . . . . . . . . . . . . . . 95
G. Ausiello and
U. Nanni and
G. F. Italiano Dynamic maintenance of directed
hypergraphs . . . . . . . . . . . . . . 97--117
E. Engeler Combinatory differential fields . . . . 119--131
R. Echahed On completeness of narrowing strategies 133--146
J. Francon and
B. Randrianarimanana and
R. Schott Analysis of dynamic algorithms in
Knuth's model . . . . . . . . . . . . . 147--167
I. Gnaedig and
C. Kirchner and
H. Kirchner Equational completion in order-sorted
algebras . . . . . . . . . . . . . . . . 169--202
R. Gorrieri and
S. Marchetti and
U. Montanari $A^2 CCS$: atomic actions for $CCS$ . . 203--223
R. Kennaway Implementing term rewrite languages in
Dactl . . . . . . . . . . . . . . . . . 225--249
R. Klein and
D. Wood A tight upper bound for the path length
of AVL trees . . . . . . . . . . . . . . 251--264
K. G. Larsen Proof systems for satisfiability in
Hennessy--Milner Logic with recursion 265--288
G. Jacopini and
G. Sontacchi Reversible parallel computation: an
evolving space-model . . . . . . . . . . 1--46
F. Kroger On the interpretability of arithmetic in
temporal logic . . . . . . . . . . . . . 47--60
C. Lavault Exact average message complexity values
for distributed election on
bidirectional rings of processors . . . 61--79
S. Varricchio Factorizations of free monoids and
unavoidable regularities . . . . . . . . 81--89
M. Jerrum and
A. Sinclair Fast uniform generation of regular
graphs . . . . . . . . . . . . . . . . . 91--100
H. Huwig and
A. Poigne A note on inconsistencies caused by
fixpoints in a Cartesian closed category 101--112
H. Ganzinger Foreword . . . . . . . . . . . . . . . . 119
A. Aiken A theory of compaction-based
parallelization . . . . . . . . . . . . 121--154
You-Chin C. Fuh and
P. Mishra Type inference with subtypes . . . . . . 155--175
R. Giegerich Code selection by inversion of
order-sorted derivors . . . . . . . . . 177--211
S. Horwitz Adding relational query facilities to
software development environments . . . 213--230
P. Wadler Deforestation: transforming programs to
eliminate trees . . . . . . . . . . . . 231--248
R. Beigel Bi-immunity results for cheatable sets 249--263
Jian-er Chen The difference between one tape and two
tapes: with respect to reversal
complexity . . . . . . . . . . . . . . . 265--278
J. Hoffmann and
M. G. Main Results on NLC grammars with one-letter
terminal alphabets . . . . . . . . . . . 279--294
Changwook Kim Complexity and decidability for
restricted classes of picture languages 295--311
J. M. Robson Strong time bounds: non-computable
bounds and a hierarchy theorem . . . . . 313--317
A. A. Bertossi and
F. Luccio and
E. Lodi and
L. Pagli String matching with weighted errors . . 319--328
T. Head The set of strings mapped into a
submonoid by iterates of a morphism . . 329--333
W. Schmitt Hopf algebras and identities in free
partially commutative monoids . . . . . 335--340
V. Diekert Word problems over traces which are
solvable in linear time . . . . . . . . 3--18
D. Fussell and
R. Thurimella Successive approximation in parallel
graph algorithms . . . . . . . . . . . . 19--35
A. Gavilanes-Franco and
F. Lucio-Carrasco A first order logic for partial
functions . . . . . . . . . . . . . . . 37--69
P. Jancar Decidability of a temporal logic problem
for Petri nets . . . . . . . . . . . . . 71--93
F. P. Preparata and
R. Tamassia Dynamic planar point location with
optimal query time . . . . . . . . . . . 95--114
A. Szepietowski If deterministic and nondeterministic
space complexities are equal for $\log
\log n$, then they are also equal for
$\log n$ . . . . . . . . . . . . . . . . 115--119
P. Gastin An asynchronous model for distributed
systems . . . . . . . . . . . . . . . . 121--162
F. Gecseg and
H. Jurgensen Automata represented by products of
soliton automata . . . . . . . . . . . . 163--181
B. J. Oommen and
E. R. Hansen and
J. I. Munro Deterministic optimal and expedient
move-to-rear list organizing strategies 183--197
F. Okulicka On priority in COSY . . . . . . . . . . 199--216
J. Hartmanis and
L. A. Hemachandra Robust machine saccept easy sets . . . . 217--225
M. Bezem Completeness of resolution revisited . . 227--237
H. Huttel SnS can be modally characterized . . . . 239--248
M. Kummer An easy priority-free proof of a theorem
of Friedberg . . . . . . . . . . . . . . 249--251
Jingzhong Zhang and
Lu Yang and
M. Deng The parallel numerical method of
mechanical theorem proving . . . . . . . 253--271
R. Casas and
M.-I. Fernandez-Camacho and
J.-M. Steyaert Algebraic simplification in computer
algebra: an analysis of bottom-up
algorithms . . . . . . . . . . . . . . . 273--298
Xin He An efficient algorithm for edge coloring
planar graphs with Delta colors . . . . 299--312
L. Babai and
P. Pudlak and
V. Rodl and
E. Szemeredi Lower bounds to the complexity of
symmetry Boolean functions . . . . . . . 313--323
U. Hertrampf Relations among mod-classes . . . . . . 325--328
J.-F. Romeuf A polynomial algorithm for solving
systems of two linear Diophantine
equations . . . . . . . . . . . . . . . 329--340
M. Anselmo On zigzag codes and their decidability 341--354
J. Szymanski On the complexity of algorithms on
recursive trees . . . . . . . . . . . . 355--361
Anonymous International Conference on Fifth
Generation Computer Systems 1988 . . . . ??
R. Milner Interpreting one concurrent calculus in
another . . . . . . . . . . . . . . . . 3--13
J. W. de Bakker and
J. N. Kok Comparative metric semantics for
Concurrent Prolog . . . . . . . . . . . 15--43
M. Falaschi and
G. Levi Finite failures and partial computations
in concurrent logic languages . . . . . 45--66
M. Murakami A declarative semantics of flat guarded
Horn clauses for programs with perpetual
processes . . . . . . . . . . . . . . . 67--83
S. Holldobler Conditional equational theories and
complete sets of transformations . . . . 85--110
N. Dershowitz and
M. Okada A rationale for conditional equational
programming . . . . . . . . . . . . . . 111--138
T. Kawamura and
T. Kanamori Preservation of stronger equivalence in
unfold/fold logic program transformation 139--156
P. Devienne Weighted graphs: a tool for studying the
halting problem and time complexity in
term rewriting systems and logic
programming . . . . . . . . . . . . . . 157--215
P. Degano and
R. De Nicola and
U. Montanari A partial ordering semantics for CCS . . 223--262
S. Katz and
D. Peled Interleaving set temporal logic . . . . 263--287
M. Droste and
R. Gobel Non-deterministic information systems
and their domains . . . . . . . . . . . 289--309
U. Blass and
A. S. Fraenkel The Sprague-Grundy function for
Wythoff's game . . . . . . . . . . . . . 311--333
E. Allender and
C. Wilson Downward translations of equality . . . 335--346
J. Du and
J. Y.-T. Leung and
G. H. Young Minimizing mean flow time with release
time constraint . . . . . . . . . . . . 347--355
T. Lengauer and
K. W. Wagner The binary network flow problem is
logspace complete for P . . . . . . . . 357--363
A. J. Bonner Hypothetical datalog: complexity and
expressibility . . . . . . . . . . . . . 3--51
A. Ohori Semantics of types for database objects 53--91
D. Karabeg and
V. Vianu Parallel update transactions . . . . . . 93--114
U. W. Lipeck Transformation of dynamic integrity
constraints into transaction
specifications . . . . . . . . . . . . . 115--142
Guozhu Dong and
S. Ginsburg On the decomposition of datalog program
mappings . . . . . . . . . . . . . . . . 143--177
J. N. Kok and
J. J. M. M. Rutten Contractions in comparing concurrency
semantics . . . . . . . . . . . . . . . 179--222
Y. Sakakibara Learning context-free grammars from
structural data in polynomial time . . . 223--242
E. Timmerman The three subfamilies of rational
omega-languages closed under
omega-transduction . . . . . . . . . . . 243--250
P. Weil Products of languages with counter . . . 251--260
S. Tirri The congruence theory of closure
properties of regular tree languages . . 261--271
K. Hashiguchi and
H. Yoo Extended regular expressions of star
degree at most two . . . . . . . . . . . 273--284
A. Petit Distribution and synchronized automata 285--308
S. Yamasaki Recursion equation sets computing logic
programs . . . . . . . . . . . . . . . . 309--322
T. Jiang On the complexity of $1$-tape ATMs and
off-line $1$-tape ATMs running in
constant reversals . . . . . . . . . . . 323--330
E. Gannett and
S. C. Kothari and
H.-C. Yen On optimal parallelization of sorting
networks . . . . . . . . . . . . . . . . 331--341
R. Sarnath and
Xin He A P-Complete Graph Partition Problem . . 343--351
Anonymous International Conference on Algebraic
Methodology and Software Technology,
AMAST . . . . . . . . . . . . . . . . . ??
T. Rus Editorial . . . . . . . . . . . . . . . 1
L. Bradley Abstract language design . . . . . . . . 5--26
H. Ehrig and
W. Fey and
H. Hansen and
M. Lowe and
D. Jacobs and
F. Parisi-Presicce Compatibility problems in the
development of algebraic module
specifications . . . . . . . . . . . . . 27--71
S. Even and
D. A. Schmidt Category-sorted algebra-based action
semantics . . . . . . . . . . . . . . . 73--95
R. Janicki and
T. Muldner Transformations of sequential
specifications into concurrent
specifications by synchronization guards 97--129
V. Manca and
A. Salibra and
G. Scollo Equational type logic . . . . . . . . . 131--159
D. Pigozzi Data types over multiple-valued logics 161--194
E. G. Wagner An algebraically specified language for
data directed design . . . . . . . . . . 195--219
S. Toda Positive relativizations for log space
computability . . . . . . . . . . . . . 221--235
S. Bozapalidis Effective constructions on formal series
of trees . . . . . . . . . . . . . . . . 237--247
C. H. Smith and
M. Velauthapillai On the inference of approximate programs 249--266
Y. Kawahara Pushout-complements and basic concepts
of grammars in toposes . . . . . . . . . 267--289
P. Atzeni and
E. P. F. Chan Efficient and optimal query answering on
independent schemes . . . . . . . . . . 291--308
W. F. Dowling and
R. Kline The fixed points of logic programs with
Herbrand base $N$ . . . . . . . . . . . 309--319
H. M. A. Fahmy Analysis of Petri nets by partitioning:
splitting transitions . . . . . . . . . 321--330
M. Elbaz and
J.-C. Spehner Construction of Voronoi diagrams in the
plane by using maps . . . . . . . . . . 331--343
Anonymous Workshop on Deductive Database Theory ??
N. Bidoit Negation in rule-based database
languages: a survey . . . . . . . . . . 3--83
N. Bidoit and
C. Froidevaux Negation by default and unstratifiable
logic programs . . . . . . . . . . . . . 85--112
V. Royer The semantics of incomplete databases as
an expression of preferences . . . . . . 113--136
S. Abiteboul and
E. Simon Fundamental properties of deterministic
and nondeterministic extensions of
Datalog . . . . . . . . . . . . . . . . 137--158
S. Abiteboul and
P. Kanellakis and
G. Grahne On the representation and querying of
sets of possible worlds . . . . . . . . 159--187
J. P. Delahaye and
V. Thibau Programming in three-valued logic . . . 189--216
B. Courcelle Recursive queries and context-free graph
grammars . . . . . . . . . . . . . . . . 217--244
R. Demolombe An efficient strategy for non-Horn
deductive databases . . . . . . . . . . 245--259
J. Engelfriet and
H. Vogler Modular tree transducers . . . . . . . . 267--303
R. Downey On computational complexity and honest
polynomial degrees . . . . . . . . . . . 305--317
R. Konig Graphs and free partially commutative
monoids . . . . . . . . . . . . . . . . 319--346
T. Harju and
J. Karhumaki The equivalence problem of multitape
finite automata . . . . . . . . . . . . 347--355
D. A. M. Barrington and
J. Corbett A note on some languages in uniform
ACC$^0$ . . . . . . . . . . . . . . . . 357--362
R. A. Baeza-Yates Searching subsequences . . . . . . . . . 363--376
G. Burosch and
J. Demetrovics and
G. O. H. Katona and
Kleitman and
D. J. and
A. A. Sapozhenko On the number of databases and closure
operations . . . . . . . . . . . . . . . 377--381
M. Anselmo The zig-zag power series: a two-way
version of the * operator . . . . . . . 3--24
A. Bertoni and
D. Bruschi and
M. Goldwurm Ranking and formal power series . . . . 25--35
P. Flajolet and
B. Salvy and
P. Zimmermann Automatic average-case analysis of
algorithms . . . . . . . . . . . . . . . 37--109
D. Krob Some examples of formal series used in
non-commutative algebra . . . . . . . . 111--135
W. Kuich Automata and languages generalized to
omega-continuous semirings . . . . . . . 137--150
C. Hespel and
G. Jacob Approximation of nonlinear dynamic
systems by rational series . . . . . . . 151--162
V. Hoang Ngoc Minh Evaluation transform . . . . . . . . . . 163--177
P. Leroux and
X. G. Viennot A combinatorial approach to nonlinear
functional expansions: an introduction
with an example . . . . . . . . . . . . 179--193
N. E. Oussous Computation, on Macsyma, of the Minimal
Differential Representation of
Noncommutative Polynomials . . . . . . . 195--207
M. Delest Enumeration of Polyominoes Using Macsyma 209--226
G. Duchamp Orthogonal projection onto the free Lie
algebra . . . . . . . . . . . . . . . . 227--239
P.-V. Koseleff Word games in free Lie algebras: several
bases and formulas . . . . . . . . . . . 241--256
F. Rotella Shuffle product of generating series . . 257--261
J. Honkala On algebraic generalized zeta functions
of formal power series . . . . . . . . . 263--273
F. W. Vaandrager Determinism to (event structure
isomorphism=step sequence equivalence) 275--294
M. Holden Weak logic theory . . . . . . . . . . . 295--321
A. Jaoua and
A. Mili and
N. Boudriga and
J. L. Durieux Regularity of relations: a measure of
uniformity . . . . . . . . . . . . . . . 323--339
A. Szalas On strictly arithmetical completeness in
logics of programs . . . . . . . . . . . 341--355
A. Stoughton Interdefinability of parallel operations
in PCF . . . . . . . . . . . . . . . . . 357--358
A. Jung The dependent product construction in
various categories of domains . . . . . 359--363
G. Koletsos Polymorphic lambda calculus: the
Church--Rosser property . . . . . . . . 365--371
W. Reisig Petri nets and algebraic specifications 1--34
F. Gecseg and
H. Jurgensen On $\alpha_0$-$\nu_1$-products of
automata . . . . . . . . . . . . . . . . 35--51
S. Heilbrunner and
L. Schmitz An efficient recognizer for the Boolean
closure of context-free languages . . . 53--75
R. R. Howell and
L. E. Rosier and
Hsu-Chun Yen Global and local views of state fairness 77--104
P. Powell and
Viet Ngo Complexity of optimal vector code
generation . . . . . . . . . . . . . . . 105--115
G. Hofer Experiments and stability in group
automata . . . . . . . . . . . . . . . . 117--120
H. Andreka and
I. Nemeti and
I. Sain On the strength of temporal proofs . . . 125--151
B. Courcelle The monadic second-order logic of
graphs. V. On closing the gap between
definability and recognizability . . . . 153--202
L. A. Hemachandra and
A. Hoene and
D. Siefkes and
P. Young On sets polynomially enumerable by
iteration . . . . . . . . . . . . . . . 203--225
S. Iwanowski Testing approximate symmetry in the
plane is NP-hard . . . . . . . . . . . . 227--262
E.-R. Olderog Correctness of concurrent processes . . 263--288
D. Ranjan and
R. Chang and
J. Hartmanis Space bounded computations: review and
new separation results . . . . . . . . . 289--302
B. Steffen and
J. Knoop Finite constants: characterizations of a
new decidable set of constants . . . . . 303--318
D. Szczepanska A Hoare-like verification system for a
language with an exception handling
mechanism . . . . . . . . . . . . . . . 319--335
J. Wiedermann On the computational efficiency of
symmetric neural networks . . . . . . . 337--345
Z. Fulop and
S. Vagvolgyi A complete classification of
deterministic root-to-frontier tree
transformation classes . . . . . . . . . 1--15
J.-M. Boe The boxes (automata theory) . . . . . . 17--34
Shouwen Tang and
R. V. Book Polynomial-time reducibilities and
`almost all' oracle sets . . . . . . . . 35--47
O. Dubois Counting the number of solutions for
instances of satisfiability . . . . . . 49--64
O. Dubois and
J. Carlier Probabilistic approach to the
satisfiability problem . . . . . . . . . 65--75
M. Piotrow On the complexity of counting in the
polynomial hierarchy . . . . . . . . . . 77--95
A. Amir and
G. M. Landau Fast parallel and serial
multidimensional approximate array
matching . . . . . . . . . . . . . . . . 97--115
F. Matus Abstract functional dependency
structures . . . . . . . . . . . . . . . 117--126
J. H. Lutz An upward measure separation theorem . . 127--135
H. Leung Limitedness theorem on finite automata
with distance functions: an algebraic
proof . . . . . . . . . . . . . . . . . 137--145
R. Cori and
M. R. Formisano On the number of partially Abelian
square-free words on a three-letter
alphabet . . . . . . . . . . . . . . . . 147--153
J. Hartmanis One-way functions and the nonisomorphism
of NP-complete sets . . . . . . . . . . 155--163
D. Kapur and
D. Musser and
P. Narendran and
J. Stillman Semi-unification . . . . . . . . . . . . 169--187
S. N. Khadilkar and
S. Biswas Padding, commitment and
self-reducibility . . . . . . . . . . . 189--199
K. Pingali and
K. Ekanadham Accumulators: new logic variable
abstractions for functional languages 201--221
K. S. H. S. R. Bhatta and
H. Karnick A resolution rule for well-formed
formulae . . . . . . . . . . . . . . . . 223--235
H. L. Bodlaender New lower bound techniques for
distributed leader finding and other
problems on rings of processors . . . . 237--256
K. Lenz and
I. Wegener The conjunctive complexity of quadratic
Boolean functions . . . . . . . . . . . 257--268
P. R. J. Asveld Abstract grammars based on transductions 269--288
J. Dassow On the connectedness of pictures in
chain code picture languages . . . . . . 289--294
To-Yat Cheung and
Yunzhou Zhu Recognizing different types of
beta-cycles in a database scheme . . . . 295--304
E. Csuhaj-Varju and
J. Kelemen On the power of cooperation: a regular
representation of recursively enumerable
languages . . . . . . . . . . . . . . . 305--310
M. Chytil and
M. Crochemore and
B. Monien and
W. Rytter On the parallel recognition of
unambiguous context-free languages . . . 311--316
N. Megiddo and
C. H. Papadimitriou On total functions, existence theorems
and computational complexity . . . . . . 317--324
K. Weihrauch and
C. Kreitz Type $2$ computational complexity of
functions on Cantor's space . . . . . . 1--18
B. Lando Periodicity and ultimate periodicity of
D0L systems . . . . . . . . . . . . . . 19--33
J.-J. Hebrard An algorithm for distinguishing
efficiently bit-strings by their
subsequences . . . . . . . . . . . . . . 35--49
K.-I. Ko On adaptive versus nonadaptive bounded
query machines . . . . . . . . . . . . . 51--69
F. Mignosi On the number of factors of Sturmian
words . . . . . . . . . . . . . . . . . 71--84
M. Snir Size-depth trade-offs for monotone
arithmetic circuits . . . . . . . . . . 85--93
J. Engelfriet and
G. Leih and
G. Rozenberg Nonterminal separation in graph grammars 95--111
M. Dietzfelbinger and
W. Maass and
G. Schnitger The complexity of matrix transposition
on one-tape off-line Turing machines . . 113--129
K. Salomaa and
S. Yu Decidability of structural equivalence
of E0L grammars . . . . . . . . . . . . 131--139
J. M. Robson An O(T log T) reduction from RAM
computations to satisfiability . . . . . 141--149
C. Calude and
G. Istrate Determining and stationary sets for some
classes of partial recursive functions 151--155
V. Palko and
O. Sykora and
I. Vrto Area complexity of merging . . . . . . . 157--163
J. M. I. M. Leo A general context-free parsing algorithm
running in linear time on every LR(k)
grammar without using lookahead . . . . 165--176
M. Bauderon Infinite hypergraphs. I. Basic
properties . . . . . . . . . . . . . . . 177--214
G. M. Germano and
S. Mazzanti Closure functions and general iterates
as reflectors . . . . . . . . . . . . . 215--252
M. Abadi and
L. Lamport The existence of refinement mappings . . 253--284
J. C. M. Baeten and
J. A. Bergtstra Recursive process definitions with the
state operator . . . . . . . . . . . . . 285--302
A. Lukassen and
G. Vossen A formal framework for independence with
respect to transactions in the universal
relation model . . . . . . . . . . . . . 303--327
W. Szwast On Horn spectra . . . . . . . . . . . . 329--339
R. R. Howell and
L. E. Rosier and
Hsu-Chun Yen A taxonomy of fairness and temporal
logic problems for Petri nets . . . . . 341--372
F. Denis and
J.-P. Delahaye Is there an axiomatic semantics for
standard pure Prolog? . . . . . . . . . 373--388
P.-L. Curien An abstract framework for environment
machines . . . . . . . . . . . . . . . . 389--402
E. Badouel and
P. Darondeau On guarded recursion . . . . . . . . . . 403--408
R. Hoofman Weakly expressive models for Hoare logic 409--418
V. Breazu-Tannen and
J. Gallier Polymorphic rewriting conserves
algebraic strong normalization . . . . . 3--28
F. Cardone Recursive types for Fun . . . . . . . . 29--56
L. Colson About primitive recursive algorithms . . 57--69
N. Dershowitz and
S. Kaplan and
D. A. Plaisted Rewrite, rewrite, rewrite, rewrite,
rewrite . . . . . . . . . . . . . . . . 71--96
Z. Manna and
A. Pnueli Completing the temporal picture (logic) 97--130
F. Parisi-Presicce Foundations of rule-based design of
modular systems . . . . . . . . . . . . 131--155
G. Winskel A note on model checking the modal
$\nu$-calculus . . . . . . . . . . . . . 157--167
H. Luchkardt New formally undecidable propositions:
non-trivial lower bounds on proof
complexity and related theorems . . . . 169--188
D. Mauro Derived linear systems of context-free
grammars . . . . . . . . . . . . . . . . 189--203
M. J. M. de Boer and
A. Lindenmayer and
Z. Tuza A periodic division pattern that cannot
be generated by D0L systems . . . . . . 205--218
S. Labhalla Computational complexity of continuous
fraction real number development . . . . 219--235
S. Seki and
Y. Kobuchi On standard locally catenative L schemes 237--248
E. Fachini and
A. M. Schettini and
G. Resta and
D. Sangiorgi Nonacceptability criteria and closure
properties for the class of languages
accepted by binary systolic tree
automata . . . . . . . . . . . . . . . . 249--260
G. Kuster On the Hurwitz product of formal power
series and automata . . . . . . . . . . 261--273
Y. Azar Parallel comparison merging of
many-ordered lists . . . . . . . . . . . 275--285
S. Kundu Minimal strings in a regular language
with respect to a partial order on the
alphabet . . . . . . . . . . . . . . . . 287--300
J. Cohen-Chesnot On the expressive power of temporal
logic for infinite words . . . . . . . . 301--312
L. A. Hemachandra and
G. Wechsung Kolmogorov characterizations of
complexity classes . . . . . . . . . . . 313--322
A. W. Mostowski Hierarchies of weak automata and weak
monadic formulas . . . . . . . . . . . . 323--335
O. Watanabe On the $p$-isomorphism conjecture . . . 337--343
D. Beauquier and
J.-E. Pin Languages and scanners . . . . . . . . . 3--21
G. Brassard and
C. Crepeau and
M. Yung Constant-round perfect zero-knowledge
computationally convincing protocols . . 23--52
V. Bruyere Maximal codes with bounded deciphering
delay . . . . . . . . . . . . . . . . . 53--76
B. Chazelle and
H. Edelsbrunner and
L. J. Guibas and
M. Sharir A singly exponential stratification
scheme for real semi-algebraic varieties
and its applications . . . . . . . . . . 77--105
G. Gambosi and
E. Nardelli and
M. Talamo A pointer-free data structure for
merging heaps and min-max heaps . . . . 107--126
C. H. Papadimitriou and
M. Yannakakis Shortest paths without a map . . . . . . 127--150
M. Clausen and
A. Dress and
J. Grabmeier and
M. Karpinski On zero-testing and interpolation of
$k$-sparse multivariate polynomials over
finite fields . . . . . . . . . . . . . 151--164
A. Saoudi Generalized automata on infinite trees
and Muller-McNaughton's theorem . . . . 165--177
S. Moran and
Y. Wolfstahl Optimal covering of cacti by
vertex-disjoint paths . . . . . . . . . 179--197
R. Beigel Bounded queries to SAT and the Boolean
hierarchy . . . . . . . . . . . . . . . 199--223
B. Becker and
U. Sparmann Computations over finite monoids and
their test complexity . . . . . . . . . 225--250
C. P. Rupert Which Kleene semigroups are finite? . . 251--264
H. A. Maurer and
A. Salomaa and
D. Wood Bounded delay L codes . . . . . . . . . 265--279
J. Dassow and
H. Jurgensen Deterministic soliton automata with a
single exterior node . . . . . . . . . . 281--292
W. A. Baldwin and
G. O. Strawn Multidimensional trees . . . . . . . . . 293--311
Jie Wang On $p$-creative sets and $p$-completely
creative sets . . . . . . . . . . . . . 1--31
J. Devolder and
I. Litovsky Finitely generated bi omega-languages 33--52
O. H. Ibarra and
Tao Jiang and
Hui Wang Parallel parsing on a one-way linear
array of finite-state machines . . . . . 53--74
S. Lindell An analysis of fixed-point queries on
binary trees . . . . . . . . . . . . . . 75--95
P. H. Rodenburg Algebraic specifiability of data types
with minimal computable parameters . . . 97--116
W. Szpankowski A characterization of digital search
trees from the successful search
viewpoint . . . . . . . . . . . . . . . 117--134
M. Kutylowski Multihead one-way finite automata . . . 135--153
I. Wegener The complexity of the parity function in
unbounded fan-in, unbounded depth
circuits . . . . . . . . . . . . . . . . 155--170
A. Cherubini and
C. Citrini and
S. C. Reghizzi and
D. Mandrioli QRT FIFO automata, breadth-first
grammars and their relations . . . . . . 171--203
P. Michel An NP-complete language accepted in
linear time by a one-tape Turing machine 205--212
M. Cialdea Resolution for some first-order modal
systems . . . . . . . . . . . . . . . . 213--229
N. Doggaz and
C. Kirchner Completion for unification . . . . . . . 231--251
E. Sopena Hypermap rewriting: a combinatorial
approach . . . . . . . . . . . . . . . . 253--281
R. D. Tennent and
J. K. Tobin Continuations in possible-world
semantics . . . . . . . . . . . . . . . 283--303
J. Kamper Nonuniform proof systems: a new
framework to describe nonuniform and
probabilistic complexity classes . . . . 305--331
S. Goto Proof normalization with nonstandard
objects . . . . . . . . . . . . . . . . 333--351
I. Bethke Coherence spaces are untopological . . . 353--357
Anonymous 6th International Conference on Logic
Programming (ICLP 89) . . . . . . . . . ??
F. S. de Boer and
J. J. M. M. Rutten and
J. N. Kok and
C. Palamidessi Semantic models for concurrent logic
languages . . . . . . . . . . . . . . . 3--33
R. N. Bol and
K. R. Apt and
J. W. Klop An analysis of loop checking mechanisms
for logic programs . . . . . . . . . . . 35--79
L. Cavedon Acyclic logic programs and the
completeness of SLDNF-resolution . . . . 81--92
J. Lobo and
A. Rajasekar and
J. Minker Semantics of Horn and disjunctive logic
programs . . . . . . . . . . . . . . . . 93--106
H. Seki Unfold/fold transformation of stratified
programs . . . . . . . . . . . . . . . . 107--139
A. Averbuch and
Z. Galil and
S. Winograd Classification of all the minimal
bilinear algorithms for computing the
coefficients of the product of two
polynomials modulo a polynomial. II. The
algebra $ G(u)(u^n) $ . . . . . . . . . 143--203
J.-C. Spehner Merging in maps and in pavings . . . . . 205--232
K. Hashiguchi Recognizable closures and submonoids of
free partially commutative monoids . . . 233--241
M. Chrobak and
D. Eppstein Planar orientations with low out-degree
and compaction of adjacency matrices . . 243--266
M. Krause and
C. Meinel and
S. Waack Separating the eraser Turing machine
classes $L_e$, $\hbox{NL}_e$,
$\hbox{co-NL}_e$ and $P_e$ . . . . . . . 267--275
F. Gire and
M. Nivat Algebraic languages of biinfinite words 277--323
A. Bertoni and
M. Goldwurm and
N. Sabadini The complexity of computing the number
of strings of given length in
context-free languages . . . . . . . . . 325--342
C.-J. Seger On the existence of speed-independent
circuits . . . . . . . . . . . . . . . . 343--364
R. M. Capocelli and
L. Gargano and
U. Vaccaro Decoders with initial state invariance
for multivalued encodings . . . . . . . 365--375
G. M. Benedek and
A. Itai Learnability with respect to fixed
distributions . . . . . . . . . . . . . 377--389
V. Stoltenberg-Hanssen and
J. V. Tucker Algebraic and fixed point equations over
inverse limits of algebras . . . . . . . 1--24
W. M. Farmer Simple second-order languages for which
unification is undecidable . . . . . . . 25--41
A. G. Heibig Control machines: a new model of
parallelism for compositional
specifications and their effective
compilation . . . . . . . . . . . . . . 43--80
H. Balsters and
M. M. Fokkinga Subtyping can have a simple semantics 81--96
R. Fournier and
G. von Bochmann The equivalence in the DCP model . . . . 97--114
L. Hallnas Partial inductive definitions . . . . . 115--142
P. Gardiner and
C. Morgan Data refinement of predicate
transformers . . . . . . . . . . . . . . 143--162
H. Zierer Relation algebraic domain constructions 163--188
A. Wilm Determinism and nondeterminism in PDL 189--202
M. Mezghiche Weak completeness of type assignment in
lambda-calculus models: a generalization
of Hindley's result . . . . . . . . . . 203--208
R. Milner and
M. Tofte Conduction in relational semantics . . . 209--220
W. McCune and
L. Wos The absence and the presence of fixed
point combinators . . . . . . . . . . . 221--228
Z. Esik Results on homomorphic realization of
automata by $\alpha_0$-products . . . . 229--249
K. Diks and
W. Rytter On optimal parallel computations for
sequences of brackets . . . . . . . . . 251--262
M. Gyssens and
D. Van Gucht A comparison between algebraic query
languages for flat and nested databases 263--286
E. Csuhaj-Varju and
J. Dassow On bounded interpretations of grammar
forms . . . . . . . . . . . . . . . . . 287--313
A. de Luca and
S. Varricchio Finiteness and iteration conditions for
semigroups . . . . . . . . . . . . . . . 315--327
N. Nirmal and
R. Rama Machine characterization of (E0L-E0L)
array languages . . . . . . . . . . . . 329--346
C. Calude Relativized topological size of sets of
partial recursive functions . . . . . . 347--352
R. Gavalda and
J. L. Balcazar Strong and robustly strong
polynomial-time reducibilities to sparse
sets . . . . . . . . . . . . . . . . . . 1--14
K. G. Larsen and
B. Thomsen Partial specifications and compositional
verification . . . . . . . . . . . . . . 15--32
S. Miyano $\Delta_2^P$-complete lexicographically
first maximal subgraph problems . . . . 33--57
M. Crochemore and
W. Rytter Usefulness of the Karp-Miller-Rosenberg
algorithm in parallel computations on
strings and arrays . . . . . . . . . . . 59--82
M. Garzon and
Y. Zalcstein The complexity of Grigorchuk groups with
application to cryptography . . . . . . 83--98
Sang Cho and
Dung T. Huynh Finite-automaton aperiodicity is
PSPACE-complete . . . . . . . . . . . . 99--116
P. Shankar and
B. S. Adiga A graph-based regularity test for
deterministic context-free languages . . 117--125
A. Salomaa A deterministic algorithm for modular
knapsack problems . . . . . . . . . . . 127--138
J. Engelfriet A regular characterization of graph
languages definable in monadic
second-order logic . . . . . . . . . . . 139--150
K. Aizawa and
A. Nakamura Graph grammars with path-controlled
embedding . . . . . . . . . . . . . . . 151--170
S. Labhalla and
H. Lombardi Representation of real numbers by
developments in whole bases and
complexity . . . . . . . . . . . . . . . 171--182
S. Khuller and
V. V. Vazirani Planar graph coloring is not
self-reducible, assuming P not=NP . . . 183--189
H. Seki and
T. Matsumura and
M. Fujii and
T. Kasami On multiple context-free grammars . . . 191--229
U. Huckenbeck A result about the power of geometric
oracle machines . . . . . . . . . . . . 231--251
K. Peeva Equivalence, reduction and minimization
of finite automata over semirings . . . 269--285
K. Inoue and
A. Ito and
I. Takanami A note on real-time one-way alternating
multicounter machines . . . . . . . . . 287--296
A. Bebjak and
I. Stefanekova Separation of deterministic,
nondeterministic and alternating
complexity classes . . . . . . . . . . . 297--311
W. Baur On the algebraic complexity of rational
iteration procedures . . . . . . . . . . 313--324
A. Weber and
H. Seidl On the degree of ambiguity of finite
automata . . . . . . . . . . . . . . . . 325--349
H. Yoo and
K. Hashiguchi Extended automata-like regular
expressions of star degree at most (2,
1) . . . . . . . . . . . . . . . . . . . 351--363
P. Seebold Fibonacci morphisms and Sturmian words 365--384
H. Ganzinger Order-sorted completion: the many-sorted
way . . . . . . . . . . . . . . . . . . 3--32
A. Habel and
H.-J. Kreowski and
W. Vogler Decidable boundedness problems for sets
of graphs generated by
hyperedge-replacement . . . . . . . . . 33--62
M. Hanus Horn clause programs with polymorphic
types: semantics and resolution . . . . 63--106
R. Harper and
R. Pollack Type checking with universes . . . . . . 107--136
F. Pfenning and
P. Lee Metacircularity in the polymorphic
$\lambda$-calculus . . . . . . . . . . . 137--159
C. Stirling and
D. Walker Local model checking in the modal
mu-calculus . . . . . . . . . . . . . . 161--177
C. A. Vissers and
G. Scollo and
M. van Sinderen and
E. Brinksma Specification styles in distributed
systems design and verification . . . . 179--206
D. Krob Complete systems of B-rational
identities . . . . . . . . . . . . . . . 207--343
D. E. Knuth Theory and practice (computer science) 1--15
I. V. Pottosin Analysis of program optimization
possibilities and further development 17--36
V. Kasyanov Transformational approach to program
concretization . . . . . . . . . . . . . 37--46
M. A. Bulyonkov From partial evaluation to mixed
computation . . . . . . . . . . . . . . 47--60
Y. Futamura and
K. Nogi and
A. Takano Essence of generalized partial
computation . . . . . . . . . . . . . . 61--79
V. E. Itkin An algebra of mixed computation . . . . 81--93
N. D. Jones Static semantics, types, and binding
time analysis . . . . . . . . . . . . . 95--118
W. M. Turski Prescribing behaviours . . . . . . . . . 119--125
J. W. de Bakker and
J. H. A. Warmerdam Four domains for concurrency . . . . . . 127--149
L. A. Cherkasova and
V. E. Kotov An algebra of concurrent
nondeterministic processes . . . . . . . 151--170
A. Mazurkiewicz and
A. Rabinovich and
B. A. Trakhtenbrot Connectedness and synchronization . . . 171--184
E. Tyugu Higher order dataflow schemas . . . . . 185--198
J. M. Barzdin and
G. J. Barzdin Rapid construction of algebraic axioms
from samples . . . . . . . . . . . . . . 199--208
A. Blikle and
A. Tarlecki and
M. Thorup On conservative extensions of syntax in
system development . . . . . . . . . . . 209--233
C. A. R. Hoare A theory for the derivation of
combinational C-MOS circuit designs . . 235--251
N. N. Nepejvoda A bridge between constructive logic and
computer programming . . . . . . . . . . 253--270
T. Rus Algebraic construction of compilers . . 271--308
M. Tatsuta Program synthesis using realizability 309--353
T. Saito Dynamics of equivalence relations in
automata networks . . . . . . . . . . . 355--367
Y. Toyama How to prove equivalence of term
rewriting systems without induction . . 369--390
Guozhu Dong and
S. Ginsburg Localizable constraints for object
histories . . . . . . . . . . . . . . . 391--432
D. Vakarelov Modal logics for knowledge
representation systems . . . . . . . . . 433--456
A. Srinivasan and
C. P. Rangan Efficient algorithms for the minimum
weighted dominating clique problem on
permutation graphs . . . . . . . . . . . 1--21
P. Buneman and
A. Jung and
A. Ohori Using powerdomains to generalize
relational databases . . . . . . . . . . 23--55
K. Culik, II and
S. Dube An efficient solution of the firing mob
problem . . . . . . . . . . . . . . . . 57--69
M. Arfi Polynomial operations and hierarchies of
concatenation . . . . . . . . . . . . . 71--84
K. Hashiguchi Algorithms for determining relative
inclusion star height and inclusion star
height . . . . . . . . . . . . . . . . . 85--100
E. B. Kinber On complete sets of samples for
generalized regular expressions . . . . 101--117
D. Moews Sums of games born on Days 2 and 3 . . . 119--128
P. Kearney and
J. Staples An extensional fixed-point semantics for
nondeterministic data flow . . . . . . . 129--179
P. M. W. Knijnenburg and
J. van Leeuwen On models for propositional dynamic
logic . . . . . . . . . . . . . . . . . 181--203
W. Vogler Executions: a new partial-order
semantics of Petri nets . . . . . . . . 205--238
A. Tarlecki and
R. M. Burstall and
J. A. Goguen Some fundamental algebraic tools for the
semantics of computation. 3. Indexed
categories . . . . . . . . . . . . . . . 239--264
Wenhui Zhang Cut elimination and automatic proof
procedures . . . . . . . . . . . . . . . 265--284
B. Rozoy and
P. S. Thiagarajan Event structures and trace monoids . . . 285--313
Anonymous Combinatorial Pattern Matching School ??
M. Crochemore Foreword to the Special Issue on
Selected Papers of the Combinatorial
Pattern Matching School, Paris, July
1990 . . . . . . . . . . . . . . . . . . 1
A. Apostolico and
S. Browne and
C. Guerra Fast linear-space computations of
longest common subsequences . . . . . . 3--17
R. A. Baeza-Yates and
M. Regnier Average running time of the
Boyer--Moore--Horspool algorithm . . . . 19--31
M. Crochemore String-matching on ordered alphabets . . 33--47
Z. Galil and
K. Park Dynamic programming with convexity,
concavity, and sparsity . . . . . . . . 49--76
K. Hashiguchi and
K. Yamada Two recognizable string-matching
problems over free partially commutative
monoids . . . . . . . . . . . . . . . . 77--86
C. S. Iliopoulos and
W. F. Smyth Optimal algorithms for computing the
canonical form of a circular string . . 87--105
J. Y. Kim and
J. Shawe-Taylor An approximate string-matching algorithm 107--117
T. Lecroq A variation on the Boyer--Moore
algorithm . . . . . . . . . . . . . . . 119--144
J. Neraud and
M. Crochemore A string matching interpretation of the
equation $x^m y^n=z^p$ . . . . . . . . . 145--164
R. W. Quong Fast average-case pattern matching by
multiplexing sparse tables . . . . . . . 165--179
D. Revuz Minimisation of acyclic deterministic
automata in linear time . . . . . . . . 181--189
E. Ukkonen Approximate string-matching with
$q$-grams and maximal matches . . . . . 191--211
M. Zipstein Data compression with factor automata 213--221
A. Ehrenfeucht and
G. Rozenberg Angular $2$-structures . . . . . . . . . 227--248
M. Goldwurm Probabilistic estimation of the number
of prefixes of a trace . . . . . . . . . 249--268
U. Hebisch and
H. J. Weinert Generalized semigroup semirings which
are zero-divisor-free or
multiplicatively left-cancellative . . . 269--289
J. Bitar and
E. Goles Parallel chip firing games on graphs . . 291--300
J. H. Lutz On independent random oracles . . . . . 301--307
L. A. Hemachandra and
R. S. Rubinstein Separating complexity classes with tally
oracles . . . . . . . . . . . . . . . . 309--318
H. Edelsbrunner and
L. Guibas and
J. Pach and
R. Pollack and
Seidel and
R. and
M. Sharir Arrangements of curves in the
plane-topology, combinatorics and
algorithms . . . . . . . . . . . . . . . 319--336
A. J. Kfoury and
J. Tiuryn and
P. Urzyczyn On the expressive power of finitely
typed and universally polymorphic
recursive procedures . . . . . . . . . . 1--41
S. Vagvolgyi Top-down tree transducers with two-way
tree walking look-ahead . . . . . . . . 43--74
G. E. Revesz A list-oriented extension of the
lambda-calculus satisfying the
Church--Rosser theorem . . . . . . . . . 75--89
P. G. Harrison and
H. Khoshnevisan A new approach to recursion removal . . 91--113
V. S. Subrahmanian Paraconsistent disjunctive deductive
databases . . . . . . . . . . . . . . . 115--141
Guo-Qiang Zhang Stable neighbourhoods . . . . . . . . . 143--157
A. Goerdt Unrestricted resolution versus
N-resolution . . . . . . . . . . . . . . 159--167
P. Peladeau Logically defined subsets of $N^k$ . . . 169--183
K. Hiraishi and
A. Ichikawa On structural conditions for weak
persistency and semilinearity of Petri
nets . . . . . . . . . . . . . . . . . . 185--199
G. Louchard and
B. Randrianarimanana and
R. Schott Dynamic algorithms in D. E. Knuth's
model: a probabilistic analysis . . . . 201--225
P. Bonizzoni and
G. Mauri On automata on infinite trees . . . . . 227--244
Z. M. Kedem and
K. V. Palem Optimal parallel algorithms for forest
and term matching . . . . . . . . . . . 245--264
S. Toda Restricted relativizations of
probabilistic polynomial time . . . . . 265--277
P. Ramanan Testing the optimality of alphabetic
trees . . . . . . . . . . . . . . . . . 279--301
J. Boyar and
G. Frandsen and
C. Sturtivant An arithmetic model of computation
equivalent to threshold circuits . . . . 303--319
P. Dehornoy A criterion for proving noetherianity of
a relation . . . . . . . . . . . . . . . 321--325
T. Herbst On a kind of Fatou property of
context-free groups . . . . . . . . . . 327--331
U. Waldmann Semantics of order-sorted specifications 1--35
F. Lamarche Quantitative domains and infinitary
algebras . . . . . . . . . . . . . . . . 37--62
I. Filippenko and
F. L. Morris Domains for logic programming . . . . . 63--69
V. Manca and
A. Salibra Soundness and completeness of the
Birkhoff equational calculus for
many-sorted algebras with possibly empty
carrier sets . . . . . . . . . . . . . . 101--124
P. Caspi Clocks in dataflow languages . . . . . . 125--140
M. Koutney Adequacy-preserving transformations of
COSY path programs . . . . . . . . . . . 141--158
C. Mauduit Introduction . . . . . . . . . . . . . . 159
J.-P. Allouche and
P. Morton and
J. Shallit Pattern spectra, substring enumeration,
and automatic sequences . . . . . . . . 161--174
L. Baratchart and
M. Olivi and
F. Wielonsky On a rational approximation problem in
the real Hardy space $H_2$ . . . . . . . 175--197
P. Dehornoy Probl\`eme de mots dans les gerbes
libres. (French) [Word problems in free
groups] . . . . . . . . . . . . . . . . 199--213
S. Ferenczi Tiling the Morse sequence . . . . . . . 215--221
Ch. Frougny Syst\`emes de numération linéaires et
theta-représentations. (French) [Linear
numeration systems and
theta-representation] . . . . . . . . . 223--236
D. Galmiche Program development in constructive type
theory . . . . . . . . . . . . . . . . . 237--259
D. Gardy Méthode de col et lois limités en analyse
combinatoire. (French) [Bottleneck
method and limit laws in combinational
analysis] . . . . . . . . . . . . . . . 261--280
B. Gil Complete extension of general logic
programs . . . . . . . . . . . . . . . . 281--294
G. Lachaud Artin--Schreier curves, exponential
sums, and coding theory . . . . . . . . 295--310
D. Mery The NU system as a development system
for concurrent programs: delta NU . . . 311--334
D. Perrin and
M. Parigot Recursive programming with proofs . . . 335--356
D. Perrin On positive matrices . . . . . . . . . . 357
A. Restivo A note on renewal systems . . . . . . . 367--371
Zhi-Xiong Wen and
Zhi-Ying Wen Some studies on the $(p,q)$-type
sequences . . . . . . . . . . . . . . . 373--393
V. Vianu and
G. Vossen Conceptual level concurrency control of
relational update transactions . . . . . 1--42
L. Giordano and
A. Martelli and
G. Rossi Extending Horn clause logic with
implication goals . . . . . . . . . . . 43--74
I. Sain Temporal logics need their clocks . . . 75--95
S. Arikawa and
T. Shinohara and
A. Yamamoto Learning elementary formal systems . . . 97--113
G. Bellin and
J. Ketonen A decision procedure revisited: Notes on
direct logic, linear logic and its
implementation . . . . . . . . . . . . . 115--142
B. Jacobs and
I. Margaria and
M. Zacchi Filter models with polymorphic types . . 143--158
S. R. Schwer Fine covers of a VAS language . . . . . 159--168
J. Beauquier Two distributed problems involving
Byzantine processes . . . . . . . . . . 169--185
J. Moulin Ollagnier Proof of Dejean's conjecture for
alphabets with 5, 6, 7, 8, 9, 10 and 11
letters . . . . . . . . . . . . . . . . 187--205
P. Quinton and
Y. Robert Systolic convolution of arithmetic
functions . . . . . . . . . . . . . . . 207--229
Y. Rabani and
Z. Galil On the space complexity of some
algorithms for sequence comparison . . . 231--244
G. Ausiello and
G. F. Italiano and
A. Marchetti Spaccamela and
U. Nanni On-line computation of minimal and
maximal length paths . . . . . . . . . . 245--261
S. Zhang Polynomial-time algorithms for testing
strong isomorphism and computing the
automorphism group of R-strongly
connected automata . . . . . . . . . . . 263--277
L. Pierre Rational indexes of generators of the
cone of context-free languages . . . . . 279--305
J. Spencer Ulam's searching game with a fixed
number of lies . . . . . . . . . . . . . 307--321
S. G. Akl and
M. Cosnard and
A. G. Ferreira Data-movement-intensive problems: two
folk theorems in parallel computation
revisited . . . . . . . . . . . . . . . 323--337
P. Shankar and
B. S. Adiga A graph-based regularity test for
deterministic context-free languages . . 339--340
Anonymous 2nd Workshop on Concurrency and
Compositionality . . . . . . . . . . . . ??
R. De Nicola and
U. Montanari Preface . . . . . . . . . . . . . . . . 1
M. Nielsen and
G. Rozenberg and
P. S. Thiagarajan Elementary transition systems . . . . . 3--33
M. Mukund and
P. S. Thiagarajan A logical characterization of well
branching event structures . . . . . . . 35--72
J. Meseguer Conditional rewriting logic as a unified
model of concurrency . . . . . . . . . . 73--155
J. Bradfield and
C. Stirling Local model checking for infinite state
spaces . . . . . . . . . . . . . . . . . 157--174
E. Best and
M. Koutny Petri net semantics of priority systems 175--215
G. Berry and
G. Boudol The chemical abstract machine . . . . . 217--248
E. Astesiano and
A. Giovini and
G. Reggio Observational structures and their
logics . . . . . . . . . . . . . . . . . 249--283
V. K. Garg and
M. T. Ragunath Concurrent regular expressions and their
relationship to Petri nets . . . . . . . 285--304
D. T. Huynh Nonuniform complexity and the randomness
of certain complete languages . . . . . 305--324
M. Ito and
H. Jurgensen and
H. J. Shyr and
G. Thierrin Languages whose $n$-element subsets are
codes . . . . . . . . . . . . . . . . . 325--344
R. Barua The Hausdorff-Kuratowski hierarchy of
omega-regular languages and a hierarchy
of Muller automata . . . . . . . . . . . 345--360
T. E. Plambeck Daisies, Kayles, and the Sibert-Conway
decomposition in misere octal games . . 361--388
T. S. Ferguson Mate with bishop and knight in
Kriegspiel (mathematical games) . . . . 389--403
G. Duchamp and
D. Krob On the partially commutative shuffle
product . . . . . . . . . . . . . . . . 405--410
A. Slobodova Some properties of space-bounded
synchronized alternating Turing machines
with universal states only . . . . . . . 411--419
J. Y. Girard and
A. Scedrov and
P. J. Scott Bounded linear logic: a modular approach
to polynomial-time computability . . . . 1--66
S. M. German Semantics and reasoning with free
procedures . . . . . . . . . . . . . . . 67--81
J. Perraud and
O. Roux and
M. Huou Operational semantics of a kernel of the
language ELECTRE . . . . . . . . . . . . 83--103
A. Monfroglio Integer programs for logic constraint
satisfaction . . . . . . . . . . . . . . 105--130
P. Darondeau and
D. Nolte and
L. Priese and
S. Yoccoz Fairness, distances and degrees . . . . 131--142
S. Baratella A completeness result for allowed
semi-strict programs with respect to
well-behaved and allowed query clauses 143--156
T. Weibel Extension of combinatory logic to a
theory of combinatory representation . . 157--173
K. Doets A slight strengthening of a theorem of
Blair and Kunen . . . . . . . . . . . . 175--181
M. W. Krentel Generalizations of Opt P to the
polynomial hierarchy . . . . . . . . . . 183--198
O. Watanabe and
Shouwen Tang On polynomial-time Turing and many-one
completeness in PSPACE . . . . . . . . . 199--215
H. Yoo and
K. Hashiguchi Extended regular expressions of
arbitrary star degrees . . . . . . . . . 217--231
D. E. Muller and
A. Saoudi and
P. E. Schupp Alternating automata, the weak monadic
theory of trees and its complexity . . . 233--244
G. Karner Nivat's theorem for pushdown transducers 245--262
R. A. Shore and
T. A. Slaman The $p$-$T$-degrees of the recursive
sets: lattice embeddings, extensions of
embeddings and the two-quantifier theory 263--284
J. Hromkovic and
S. A. Lozkin and
A. I. Rybko and
A. A. Sapozenko and
N. A. Skalikova Lower bounds on the area complexity of
Boolean circuits . . . . . . . . . . . . 285--300
G. Guaiana and
A. Restivo and
S. Salemi Star-free trace languages . . . . . . . 301--311
G. Duchamp and
G. Jacob and
D. Krob Second Workshop on Algebraic and
Computer-Theoretic Aspects of Formal
Power Series . . . . . . . . . . . . . . ??
C. Choffrut Rational relations and rational series 5--13
J. Karhumaki Multiplicities: A deterministic view of
nondeterminism . . . . . . . . . . . . . 15--25
G. Karner On transductions of formal power series
over complete semirings . . . . . . . . 27--39
S. Varricchio Rational series with coefficients in a
commutative ring . . . . . . . . . . . . 41--50
A. Bjorner and
C. Reutenauer Rationality of the Möbius function of
subword order . . . . . . . . . . . . . 53--63
M. P. Delest and
J. M. Fedou Attribute grammars are useful for
combinatorics . . . . . . . . . . . . . 65--76
G. Cauchon Séries de Malcev-Neumann sur le groupe
libre et questions de rationalité.
(French) [Malcev-Neumann series on the
free group and questions on nationality] 79--97
F. Dumas Skew power series rings with general
commutation formula . . . . . . . . . . 99--114
B. Mourrain Computable identities in the algebra of
formal matrices . . . . . . . . . . . . 115--133
S. Diop Differential-algebraic decision methods
and some applications to system theory 137--161
J.-P. Allouche and
J. Shallit The ring of $k$-regular sequences . . . 163--197
S. R. Schwer The context-freeness of the languages
associated with vector addition systems
is decidable . . . . . . . . . . . . . . 199--247
L. Santean and
J. Kari The impact of the number of cooperating
grammars on the generative power . . . . 249--262
Hsu-Chun Yen A multiparameter analysis of domino
tiling with an application to concurrent
systems . . . . . . . . . . . . . . . . 263--287
M. A. Palis and
S. M. Shende Upper bounds on recognition of a
hierarchy of non-context-free languages 289--319
Do Long Van and
Phan Trung Huy Varieties of finite monoids and
Buchi-McNaughton theorem . . . . . . . . 321--337
M. Chrobak and
L. L. Larmore HARMONIC is $3$-competitive for two
servers . . . . . . . . . . . . . . . . 339--346
T. Amtoft and
J. Larsson Traff Partial memoization for obtaining linear
time behavior of a 2DPDA . . . . . . . . 347--356
V.-E. Cazanescu and
Gh. Stefanescu A general result on abstract flowchart
schemes with applications to the study
of accessibility, reduction and
minimization . . . . . . . . . . . . . . 1--63
J. Hein Completions of perpetual logic programs 65--78
J. L. Lambert A structure to decide reachability in
Petri nets . . . . . . . . . . . . . . . 79--104
W. H. Hesselink Processes and formalisms for unbounded
choice . . . . . . . . . . . . . . . . . 105--119
L. Priese and
D. Nolte Strong fairness and ultra metrics . . . 121--140
P. S. Mulry Monads and algebras in the semantics of
partial data types . . . . . . . . . . . 141--155
S. Rajasekaran and
J. H. Reif Nested annealing: a provable improvement
to simulated annealing . . . . . . . . . 157--176
S. Bozapalidis Alphabetic tree relations . . . . . . . 177--211
J. Nummenmaa Constructing compact rectilinear planar
layouts using canonical representation
of planar graphs . . . . . . . . . . . . 213--230
J. Neraud On the rank of the subsets of a free
monoid . . . . . . . . . . . . . . . . . 231--241
O. H. Ibarra and
N. Q. Tran On space-bounded synchronized
alternating Turing machines . . . . . . 243--264
S. Zhang Efficient simplicity testing of automata 265
J. L. Balcazar and
U. Schoning Logarithmic advice classes . . . . . . . 279--290
S. Varricchio On the decidability of the equivalence
problem for partially commutative
rational power series . . . . . . . . . 291--299
O. H. Ibarra and
Tao Jiang and
Hui Wang A characterization of exponential-time
languages by alternating context-free
grammars . . . . . . . . . . . . . . . . 301--315
J. D. Fouks Tseitin's formulas revisited . . . . . . 315
B. Mosse Puissances de mots et reconnaissabilité
des points fixes d'une substitution.
(French) [Word power and recognizability
of substitutional fixed points] . . . . 327
C. T. Hoang A parallel algorithm for minimum
weighted colouring of triangulated
graphs . . . . . . . . . . . . . . . . . 335--344
J. L. Trahan and
M. C. Loui and
V. Ramachandran Multiplication, division, and shift
instructions in parallel random access
machines . . . . . . . . . . . . . . . . 1--44
A. Goerdt Characterizing complexity classes by
higher type primitive recursive
definitions . . . . . . . . . . . . . . 45--66
A. De Luca and
S. Varricchio On noncounting regular classes . . . . . 67--104
R. Holte and
L. Rosier and
I. Tulchinsky and
D. Varvel Pinwheel scheduling with two distinct
numbers . . . . . . . . . . . . . . . . 105--135
D. Benninger and
J. Schmid Effective subdirect decomposition: a
case study . . . . . . . . . . . . . . . 137--156
R. Board and
L. Pitt On the necessity of Occam algorithms . . 157--184
N. Santoro and
J. B. Sidney and
S. J. Sidney A distributed selection algorithm and
its expected communication complexity 185--204
S. Toda and
O. Watanabe Polynomial time $1$-Turing reductions
from #PH to #P . . . . . . . . . . . . . 205--221
P. Erdos and
D. F. Hsu Distributed loop network with minimum
transmission delay . . . . . . . . . . . 223--241
H. Prodinger Hypothetical analyses: approximate
counting in the style of Knuth, path
length in the style of Flajolet . . . . 243--251
P. Beame and
E. Brisson and
R. Ladner The complexity of computing symmetric
functions using threshold circuits . . . 253--265
L. S. Moss and
J. Meseguer and
J. A. Goguen Final algebras, cosemicomputable
algebras and degrees of unsolvability 267--302
M. Dezani-Ciancaglini and
J. R. Hindley Intersection types for combinatory logic 303--324
M. Bartha Foundations of a theory of synchronous
systems . . . . . . . . . . . . . . . . 325--346
Ke Wang On characterizing boundedness of
database schemes with bounded
dependencies . . . . . . . . . . . . . . 347--364
R. J. R. Back and
J. Von Wright Combining angels, demons and miracles in
program specifications . . . . . . . . . 365--383
K. Meinke Universal algebra in higher types . . . 385--417
E. Grandjean Editorial . . . . . . . . . . . . . . . 1
B. Courcelle The monadic second-order logic of graphs
VII: Graphs as relational structures . . 3--33
E. Gradel Capturing complexity classes by
fragments of second-order logic . . . . 35--57
J. Mazoyer and
N. Reimen A linear speed-up theorem for cellular
automata . . . . . . . . . . . . . . . . 59--98
P. Michel A survey of space complexity . . . . . . 99--132
P. Peladeau Formulas, regular languages and Boolean
circuits . . . . . . . . . . . . . . . . 133--141
M. de Rougemont The functional dimension of inductive
definitions . . . . . . . . . . . . . . 143--158
M. Z. Kwiatkowska Editorial . . . . . . . . . . . . . . . 159
Eike Best and
Jörg Desel and
Javier Esparza Traps characterize home states in free
choice systems . . . . . . . . . . . . . 161--176
Stephen Brookes and
Shai Geva Towards a theory of parallel algorithms
on concrete data structures . . . . . . 177--221
Bard Bloom and
Albert R. Meyer Experimenting with process equivalence 223--237
F. S. de Boer and
J. N. Kok and
C. Palamidessi and
J. J. M. M. Rutten From failure to success: comparing a
denotational and a declarative semantics
for Horn clause logic . . . . . . . . . 239--263
Jeremy Gunawardena Causal automata . . . . . . . . . . . . 265--288
J. J. M. Hooman and
S. Ramesh and
W. P. de Roever A compositional axiomatization of
Statecharts . . . . . . . . . . . . . . 289--335
Shmuel Katz and
Doron Peled Defining conditional independence using
collapses . . . . . . . . . . . . . . . 337--359
Klaus Grue Map theory . . . . . . . . . . . . . . . 1--134
S. Van Bakel Complete restrictions of the
intersection type discipline . . . . . . 135--163
R. Devillers Maximality preserving bisimulation . . . 165--183
J. Esparza and
M. Silva A polynomial-time algorithm to decide
liveness of bounded free choice nets . . 185--205
K. Dosen Nonmodal classical linear predicate
logic is a fragment of intuitionistic
linear logic . . . . . . . . . . . . . . 207--214
D. Bruschi Strong separations of the polynomial
hierarchy with oracles: constructive
separations by immune and simple sets 215--252
M. Skubiszewski Binary periodic synchronizing sequences 253--281
P. Dagum and
M. Luby Approximating the permanent of graphs
with large factors . . . . . . . . . . . 283--305
R. Mirwald and
C. P. Schnorr The multiplicative complexity of
quadratic Boolean forms . . . . . . . . 307--328
Liam Halpenny and
Christopher J. Smyth A classification of minimal
standard-path $2\times2$ switching
networks . . . . . . . . . . . . . . . . 329--354
L. Prasad and
S. S. Iyengar An asymptotic equality for the number of
necklaces in a shuffle-exchange network 355--365
C. Choffrut and
Th Lengaur Editorial . . . . . . . . . . . . . . . 1
R. Beigel and
J. Gill Counting classes: thresholds, parity,
mods, and fewness . . . . . . . . . . . 3--23
Jin-Yi Cai and
A. Condon and
R. J. Lipton On games of incomplete information . . . 25--38
M. Clerbout and
Y. Roos Semicommutations and algebraic languages 39--49
A. Corradini and
U. Montanari An algebraic semantics for structured
transition systems and its applications
to logic programs . . . . . . . . . . . 51--106
G. Das and
D. Joseph Minimum vertex hulls for polyhedral
domains . . . . . . . . . . . . . . . . 107--135
J. L. Lambert Sorting the sums $(x_i+y_j)$ in $O(n^2)$
comparisons . . . . . . . . . . . . . . 137--141
W. Thomas Infinite trees and automaton-definable
relations over omega-words . . . . . . . 143--159
Michel Bauderon Infinite hypergraphs II. Systems of
recursive equations . . . . . . . . . . 165--190
Kiyoharu Hamaguchi and
Hiromi Hiraishi and
Shuzo Yajima $\infty$-Regular temporal logic and its
model checking problem . . . . . . . . . 191--204
L. Palopoli Testing logic programs for local
stratification . . . . . . . . . . . . . 205--234
M. Felleisen and
R. Hieb The revised report on the syntactic
theories of sequential control and state 235--271
M. Kurihara and
A. Ohuchi Modularity of simple termination of term
rewriting systems with shared
constructors . . . . . . . . . . . . . . 273--282
Byeong Man Kim and
Jung Wan Cho A new subsumption method in the
connection graph proof procedure . . . . 283--309
C. A. Gunter The mixed powerdomain . . . . . . . . . 311--334
A. Maggiolo-Schettini and
J. Winkowski Towards an algebra for timed behaviours 335--363
W. Marek and
V. S. Subrahmanian The relationship between stable,
supported, default and autoepistemic
semantics for general logic programs . . 365--386
Harry G. Mairson A simple proof of a theorem of Statman 387--394
Thomas Streicher Independence of the induction principle
and the axiom of choice in the pure
calculus of constructions . . . . . . . 395--408
Max Dauchet Simulation of Turing machines by a
regular rewrite rule . . . . . . . . . . 409--420
A. Miola Foreword . . . . . . . . . . . . . . . . 1
Roland N. Bol Generalizing completeness results for
loop checks in logic programming . . . . 3--28
Jean-Pierre Jouannaud and
Claude Marché Termination and completion modulo
associativity, commutativity and
identity . . . . . . . . . . . . . . . . 29--51
Rolf Hennicker A semi-algorithm for algebraic
implementation proofs . . . . . . . . . 53--87
C. Limongelli and
M. Temperini Abstract specification of structures and
methods in symbolic mathematical
computation . . . . . . . . . . . . . . 89--107
Mark E. Stickel A Prolog technology theorem prover: a
new exposition and implementation in
Prolog . . . . . . . . . . . . . . . . . 109--128
Carolyn Talcott A theory for program and data type
specification . . . . . . . . . . . . . 129--159
H. Straubing and
P. Weil On a conjecture concerning dot-depth two
languages . . . . . . . . . . . . . . . 161--183
Changwook Kim and
I. H. Sudborough On reversal-bounded picture languages 185--206
Y. Takada Learning semilinear sets from examples
and via queries . . . . . . . . . . . . 207--233
D. J. Weir A geometric hierarchy beyond
context-free languages . . . . . . . . . 235--261
D. P. Bovet and
P. Crescenzi and
R. Silvestri A uniform approach to define complexity
classes . . . . . . . . . . . . . . . . 263--283
K. Jansen Processor optimization for flow graphs 285--298
René Leermakers Recursive ascent parsing: from Earley to
Marcus . . . . . . . . . . . . . . . . . 299--312
R. Leermakers and
L. Augusteijn and
F. E. J. Kruseman Aretz A functional LR parser . . . . . . . . . 313--323
Phan Minh Dung On the relations between stable and
well-founded semantics of logic programs 7--25
Kanchana Kanchanasut and
Peter J. Stuckey Transforming normal logic programs to
constraint logic programs . . . . . . . 27--56
Taisuke Sato Equivalence-preserving first-order
unfold/fold transformation systems . . . 57--84
Maurizio Gabbrielli and
Giorgio Levi Unfolding and fixpoint semantics of
concurrent constraint logic programs . . 85--128
Dieter Hofbauer Termination proofs by multiset path
orderings imply primitive recursive
derivation lengths . . . . . . . . . . . 129--140
Françoise Debart and
Patrice Enjalbert and
Madeleine Lescot Multimodal logic programming using
equational and order-sorted logic . . . 141--166
Ian Mason and
Carolyn L. Talcott Inferring the equivalence of functional
programs that mutate data . . . . . . . 167--215
Joseph A. Goguen and
José Meseguer Order sorted algebra I. Equational
deduction for multiple inheritance,
overloading, exceptions and partial
operations . . . . . . . . . . . . . . . 217--273
Ming-Hua Zhang Data types with errors and exceptions 275--299
A. Arnold Preface . . . . . . . . . . . . . . . . 1
G. Boudol and
K. G. Larsen Graphical versus logical specifications 3--20
J. Cai and
R. Paige and
R. Tarjan More efficient bottom-up multi-pattern
matching in trees . . . . . . . . . . . 21--60
D. Caucal On the regular structure of prefix
rewriting . . . . . . . . . . . . . . . 61--86
E. Kounalis Testing for the ground (co-)reducibility
property in term-rewriting systems . . . 87--117
M. I. Schwartzbach Interpretations of recursively defined
types . . . . . . . . . . . . . . . . . 119--134
H. Seidl Single-valuedness of tree transducers is
decidable in polynomial time . . . . . . 135--181
Ch. Frougny Confluent linear numeration systems . . 183--219
P. Michel Complexity of logical theories involving
coprimality . . . . . . . . . . . . . . 221--241
M. El-Taha and
S. Stidham, Jr. Deterministic analysis of queueing
systems with heterogeneous servers . . . 243--264
M. W. Bern and
H. J. Karloff and
P. Raghavan and
B. Schieber Fast geometric approximation techniques
and geometric embedding problems . . . . 265--281
R. Hausser Complexity in left-associative grammar 283--308
Hans L. Bodlaender and
Dieter Kratsch The complexity of coloring games on
perfect graphs . . . . . . . . . . . . . 309--326
J. M. Robson More languages of generalised star
height $1$ . . . . . . . . . . . . . . . 327--335
Roger Villemaire The theory of $\lfloor N + V_k,
V_l\rfloor$ is undecidable . . . . . . . 337--349
C. Damm and
Ch. Meinel Separating complexity classes related to
Omega-decision trees . . . . . . . . . . 351--360
Shou-Hsuan Stephen Huang and
Hongfei Liu and
Venkatraman Viswanathan A sublinear parallel algorithm for some
dynamic programming problems . . . . . . 361--371
K. G. Subramanian and
R. Siromoney and
L. Mathew Lyndon trees . . . . . . . . . . . . . . 373--383
A. A. Razborov On the distributional complexity of
disjointness . . . . . . . . . . . . . . 385--390
Arne Andersson Comments on ``On the balance property of
Patricia tries: External path length
viewpoint'' . . . . . . . . . . . . . . 391--393
Peter Kirschenhofer and
Helmut Prodinger and
Wojciech Szpankowski Probabilistic modeling of data
structures on words: a reply to
Professor Andersson's letter . . . . . . 395--400
A. L. Selman Foreword . . . . . . . . . . . . . . . . 1
C. Alvarez and
B. Jenner A very hard log-space counting class . . 3--30
F. Bedard and
F. Lemieux and
P. McKenzie Extensions to Barrington's M-program
model . . . . . . . . . . . . . . . . . 31--61
R. Heiman and
I. Newman and
A. Wigderson On read-once threshold formulae and
their randomized decision tree
complexity . . . . . . . . . . . . . . . 63--76
K.-J. Lange Unambiguity of circuits . . . . . . . . 77--94
J. H. Lutz and
W. J. Schmidt Circuit size relative to pseudorandom
oracles . . . . . . . . . . . . . . . . 95--120
Y. Mansour and
N. Nisan and
P. Tiwari The computational complexity of
universal hashing . . . . . . . . . . . 121--133
N. Nisan On read-once vs. multiple access to
randomness in logspace . . . . . . . . . 135--144
A. Panconesi and
D. Ranjan Quantifiers and approximation . . . . . 145--163
Bart Jacobs Comprehension categories and the
semantics of type dependency . . . . . . 169--207
Marco Bellia and
M. Eugenia Occhiuto $C$-expressions: a variable-free
calculus for equational logic
programming . . . . . . . . . . . . . . 209--252
Sachio Hirokawa Principal types of BCK-lambda-terms . . 253--276
Agostino Cortesi and
Gilberto Filé Graph properties for normal logic
programs . . . . . . . . . . . . . . . . 277--303
Michael G. Main and
David L. Black Semantic models for total correctness
and fairness . . . . . . . . . . . . . . 305--332
Vugranam Sreedhar and
Kazem Taghva Capturing strong reduction in director
string calculus . . . . . . . . . . . . 333--347
Gilles Dowek The undecidability of pattern matching
in calculi where primitive recursive
functions are representable . . . . . . 349--356
Robin Milner and
Faron Moller Unique decomposition of processes . . . 357--363
Anonymous International Colloquium on Words,
Languages and Combinatorics . . . . . . ??
M. Ito Foreword . . . . . . . . . . . . . . . . 1
Jorge Almeida Locally commutative power semigroups and
counting factors of words . . . . . . . 3--16
Sini\vsa Crvenkovi\'c and
Rozália Sz. Madarász On Kleene algebras . . . . . . . . . . . 17--24
Volker Diekert Möbius functions and confluent
semi-commutations . . . . . . . . . . . 25--43
Christiane Frougny and
Jacques Sakarovitch Synchronized rational relations of
finite and infinite words . . . . . . . 45--82
Max Garzon Cayley automata . . . . . . . . . . . . 83--102
J. Karhumäki Equations over finite sets of words and
equivalence problems in automata theory 103--118
Masashi Katsura and
Genjiro Tanaka Groups of finite elementary codes . . . 119--149
Michael Kunze Standard automata and semidirect
products of transformation semigroups 151--171
Liang Zhang and
Weide D. Qiu Decompositions of recognizable strong
maximal codes . . . . . . . . . . . . . 173--183
Z. Fulop and
F. Herrmann and
S. Vagvolgyi and
H. Vogler Tree transducers with external functions 185--236
Do Long Van and
B. Le Saec and
I. Litovsky Stability for the zigzag submonoids . . 237--249
M. Madonia and
S. Salemi and
T. Sportelli A generalization of Sardinas and
Patterson's algorithm to $z$-codes . . . 251--270
M. Dietzfelbinger and
W. Maass The complexity of matrix transposition
on one-tape off-line Turing machines
with output tape . . . . . . . . . . . . 271--290
U. Schmid The average CRI-length of a controlled
ALOHA collision resolution algorithm . . 291--310
Reuven Bar Yehuda and
Tuvi Etzion and
Shlomo Moran Rotating-table games and derivatives of
words . . . . . . . . . . . . . . . . . 311--329
Alberto Apostolico Efficient CRCW-PRAM algorithms for
universal substring searching . . . . . 331--344
Roberto Grossi On finding common subtrees . . . . . . . 345--356
Karine Slowinski Picture words with invisible lines . . . 357--363
M. Middendorf The shortest common nonsubsequence
problem is NP-complete . . . . . . . . . 365--369
Fabrizio d'Amore and
Alberto Marchetti-Spaccamela and
Umberto Nanni The weighted list update problem and the
lazy adversary . . . . . . . . . . . . . 371--384
S. Lehr Sums and rational multiples of
$q$-automatic sequences are
$q$-automatic . . . . . . . . . . . . . 385--391
Juraj Hromkovi\vc and
Katsushi Inoue A note on realtime one-way synchronized
alternating one-counter automata . . . . 393--400
Anonymous International Workshop on Computing by
Graph Transformation . . . . . . . . . . ??
B. Courcelle and
G. Rozenberg Preface . . . . . . . . . . . . . . . . 1
H. Ehrig and
M. Löwe The ESPRIT Basic Research Working Group
COMPUGRAPH: ``Computing by Graph
Transformation'': a survey . . . . . . . 3--6
Andrea Corradini and
Francesca Rossi Hyperedge replacement jungle rewriting
for term-rewriting systems and logic
programming . . . . . . . . . . . . . . 7--48
B. Courcelle and
M. Mosbah Monadic second-order evaluations on
tree-decomposable graphs . . . . . . . . 49--82
Frank Drewes Recognising $k$-connected hypergraphs in
cubic time . . . . . . . . . . . . . . . 83--122
H. Ehrig and
M. Löwe Parallel and distributed derivations in
the single-pushout approach . . . . . . 123--143
D. Janssens Equivalence of computations in actor
grammars . . . . . . . . . . . . . . . . 145--180
Michael Löwe Algebraic approach to single-pushout
graph transformation . . . . . . . . . . 181--224
Ugo Montanari and
Francesca Rossi Graph rewriting for a partial ordering
semantics of concurrent constraint
programming . . . . . . . . . . . . . . 225--256
H. J. Schneider On categorical graph grammars
integrating structural transformations
and operations on labels . . . . . . . . 257--274
Joost Engelfriet and
Hendrik Jan Hoogeboom $X$-automata on $\omega$-words . . . . . 1--51
Eric Goles and
Alejandro Maass and
Servet Martinez On the limit set of some universal
cellular automata . . . . . . . . . . . 53--78
Wayne D. Blizard Dedekind multisets and function shells 79--98
Boaz Patt-Shamir and
David Peleg Time-space tradeoffs for set operations 99--129
R. Freivalds and
E. B. Kinber and
R. Wiehagen On the power of inductive inference from
good examples . . . . . . . . . . . . . 131--144
Annegret Habel and
Hans-Jörg Kreowski and
Clemens Lautemann A comparison of compatible, finite, and
inductive graph properties . . . . . . . 145--168
Uri Zwick and
Michael S. Paterson The memory game . . . . . . . . . . . . 169--196
A. S. Fraenkel and
S. Simonson Geography (mathematical games) . . . . . 197--214
Hans L. Bodlaender Complexity of path-forming games . . . . 215--245
M. Nivat Editorial introducing the Tutorial
Section . . . . . . . . . . . . . . . . 247
Jean Gallier Constructive logics. Part I: A tutorial
on proof systems and typed
$\lambda$-calculi . . . . . . . . . . . 249--339
Bernadette Charron-Bost Coupling coefficients of a distributed
execution . . . . . . . . . . . . . . . 341--376
Michael J. Maher A transformation system for deductive
database modules with perfect model
semantics . . . . . . . . . . . . . . . 377--403
Thomas Forster A semantic characterization of the
well-typed formulae of
$\lambda$-calculus . . . . . . . . . . . 405--418
M. Sprenger and
M. Wymann-Böni How to decide the lark (combinatorial
logic) . . . . . . . . . . . . . . . . . 419--432
Anonymous Sixth Workshop on the Mathematical
Foundations of Programming Semantics . . ??
M. Mislove and
R. D. Tennent Foreword . . . . . . . . . . . . . . . . 1
Samson Abramsky Computational interpretations of linear
logic . . . . . . . . . . . . . . . . . 3--57
Reinhold Heckmann Power domains and second-order
predicates . . . . . . . . . . . . . . . 59--88
Manfred Droste On stable domains . . . . . . . . . . . 89--101
François Lamarche Stable domains are generalized
topological spaces . . . . . . . . . . . 103--123
Michael G. Main Complete proof rules for strong fairness
and strong extreme fairness . . . . . . 125--143
Hans Dybkjær and
Austin Melton Comparing Hagino's categorical
programming language and typed
lambda-calculi . . . . . . . . . . . . . 145--189
Lawrence S. Moss and
Satish R. Thatte Modal logic and algebraic specifications 191--210
Paul C. Gilmore and
George K. Tsiknis A logic for category theory . . . . . . 211--252
Paul C. Gilmore and
George K. Tsiknis Logical foundations for programming
semantics . . . . . . . . . . . . . . . 253--290
T. Rus Editorial . . . . . . . . . . . . . . . 1
Ryszard Janicki and
Maciej Koutny Structure of concurrency . . . . . . . . 5--52
Yellamraju V. Srinivas A sheaf-theoretic approach to pattern
matching and related problems . . . . . 53--97
Carolyn Talcott A theory of binding structures and
applications to rewriting . . . . . . . 99--143
Muffy Thomas and
Phil Watson Solving divergence in Knuth--Bendix
completion by enriching signatures . . . 145--185
Thomas Herbst and
Richard M. Thomas Group presentations, formal languages
and characterizations of one-counter
groups . . . . . . . . . . . . . . . . . 187--214
Richard D. Bourgin and
Sally E. Howe Shortest curves in planar regions with
curved boundary . . . . . . . . . . . . 215--253
Mitsunori Ogiwara and
Antoni Lozano On sparse hard sets for counting classes 255--275
Erzsébet Csuhaj-Varjú and
Alica Kelemenová Descriptional complexity of context-free
grammar forms . . . . . . . . . . . . . 277--289
Carl Sturtivant and
Gudmund Skovbjerg Frandsen The computational efficacy of
finite-field arithmetic . . . . . . . . 291--309
Jean Néraud Deciding whether a finite set of words
has rank at most two . . . . . . . . . . 311--337
Jean-Daniel Boissonnat and
Monique Teillaud On the randomized construction of the
Delaunay tree . . . . . . . . . . . . . 339--354
Javed A. Aslam and
Aditi Dhagat On-line algorithms for $2$-coloring
hypergraphs via chip games . . . . . . . 355--369
Aviezri S. Fraenkel and
Edward R. Scheinerman and
Daniel Ullman Undirected edge geography . . . . . . . 371--382
Cristian Calude and
Cezar Câmpeanu Note on the topological structure of
random strings . . . . . . . . . . . . . 383--390
Oscar H. Ibarra and
Nicholas Q. Trân A note on simple programs with two
variables . . . . . . . . . . . . . . . 391--397
Ivan Korec Irrational speeds of configurations
growth in generalized Pascal triangles 399--412
Jerzy Skurczy\'nski The Borel hierarchy is infinite in the
class of regular sets of trees . . . . . 413--418
Ondrej Sýkora and
Imrich Vr\vto Edge separators for graphs of bounded
genus with applications . . . . . . . . 419--420
C. Choffrut and
M. Jantzen Editorial . . . . . . . . . . . . . . . 1
Luc Albert and
Rafael Casas and
François Fages Average-case analysis of unification
algorithms . . . . . . . . . . . . . . . 3--34
Volker Diekert On the concatenation of infinite traces 35--54
Lance Fortnow and
Carsten Lund Interactive proof systems and
alternating time-space complexity . . . 55--73
Martin Hühne On the power of several queues (Turing
machines) . . . . . . . . . . . . . . . 75--91
Thierry Jéron and
Claude Jard Testing for unboundedness of fifo
channels . . . . . . . . . . . . . . . . 93--117
K. Madlener and
P. Narendran and
F. Otto and
L. Zhang On weakly confluent monadic
string-rewriting systems . . . . . . . . 119--165
Jun Tarui Probabilistic polynomials, $AC^{0}$
functions, and the polynomial-time
hierarchly . . . . . . . . . . . . . . . 167--183
Klaus Weihrauch Computability on computable metric
spaces . . . . . . . . . . . . . . . . . 191--210
Bo Yi and
Jiafu Xu Analogy calculus . . . . . . . . . . . . 211--230
Lu Ruqian A true concurrency model of CCS
semantics . . . . . . . . . . . . . . . 231--258
Jianguo Lu and
Jiafu Xu Analogical program derivation based on
type theory . . . . . . . . . . . . . . 259--272
Antonio Bucciarelli and
Thomas Ehrhard A theory of sequentiality . . . . . . . 273--291
Rob J. van Glabbeek and
Frits W. Vaandrager Modular specification of process
algebras . . . . . . . . . . . . . . . . 293--348
M. Masseron and
C. Tollu and
J. Vauzeilles Generating plans in linear logic I.
Actions as proofs . . . . . . . . . . . 349--370
M. Masseron Generating plans in linear logic. II. A
geometry of conjunctive actions . . . . 371--375
Anonymous 3rd Workshop on Concurrency and
Compositionality . . . . . . . . . . . . ??
E. Best and
G. Rozenberg Preface . . . . . . . . . . . . . . . . 1
Martín Abadi and
Gordon D. Plotkin A logical view of composition . . . . . 3--30
G. Boudol and
I. Castellani and
M. Hennessy and
A. Kiehn Observing localities . . . . . . . . . . 31--61
Pierpaolo Degano and
Rocco De Nicola and
Ugo Montanari Universal axioms for bisimulations . . . 63--91
Jörg Desel and
Javier Esparza Reachability in cyclic extended
free-choice systems . . . . . . . . . . 93--118
Kim Guldstrand Larsen The expressive power of implicit
specifications . . . . . . . . . . . . . 119--147
Robin Milner and
Joachim Parrow and
David Walker Modal logics for mobile processes . . . 149--171
Walter Vogler Bisimulation and action refinement . . . 173--200
Steven Vickers Information systems for continuous
posets . . . . . . . . . . . . . . . . . 201--229
Thomas Eiter and
Georg Gottlob Propositional circumscription and
extended closed-world reasoning are
$\Pi^P_2$-complete . . . . . . . . . . . 231--245
Jules Desharnais and
Ali Jaoua and
Fatma Mili and
Noureddine Boudriga and
Ali Mili A relational division operator: the
conjugate kernel . . . . . . . . . . . . 247--272
Daniel J. Dougherty Higher-order unification via combinators 273--298
Michael Barr Terminal coalgebras in well-founded set
theory . . . . . . . . . . . . . . . . . 299--315
Morten Elvang-Gòransson and
Olaf Owe A simple sequent calculus for partial
functions . . . . . . . . . . . . . . . 317--330
S. Abramsky and
P.-L Curien Preface . . . . . . . . . . . . . . . . 1
Richard Blute Linear logic, coherence and dinaturality 3--41
Albert Burroni Higher-dimensional word problems with
applications to equational logic . . . . 43--62
Thierry Coquand Another proof of the intuitionistic
Ramsey theorem . . . . . . . . . . . . . 63--75
Abbas Edalat and
Michael B. Smyth I-categories as a framework for solving
domain equations . . . . . . . . . . . . 77--106
P. Freyd Structural polymorphism . . . . . . . . 107--129
Grzegorz Jarzembski Programs in partial algebras . . . . . . 131--149
C. Barry Jay Tail recursion through universal
invariants . . . . . . . . . . . . . . . 151--189
Igor Litovsky and
Yves Métivier Computing with graph rewriting systems
with priorities . . . . . . . . . . . . 191--224
Eric Allender and
Richard Beigel and
Ulrich Hertrampf and
Steven Homer Almost-everywhere complexity hierarchies
for nondeterministic time . . . . . . . 225--241
Arturo Carpi Overlap-free words and finite automata 243--260
Oscar H. Ibarra and
Nicholas Q. Trân Synchronized finite automata and $2$DFA
reductions . . . . . . . . . . . . . . . 261--275
Luc Longpré and
Alan L. Selman Hard promise problems and nonuniform
complexity . . . . . . . . . . . . . . . 277--290
A. Troesch Interpretation geométrique de
l'algorithme d'Euclide et reconnaissance
de segments. (French) [Geometric
interpretation of Euclid's algorithm
with recognition segments] . . . . . . . 291--319
Eric Goles and
Marcos A. Kiwi Games on line graphs and sand piles . . 321--349
R. Srikant and
Ravi Sundaram and
Karan Sher Singh and
C. Pandu Rangan Optimal path cover problem on block
graphs and bipartite permutation graphs 351--357
Masashi Katsura and
Yuji Kobayashi The shuffle algebra and its derivations 359--369
Shouwen Tang and
Bin Fu and
Tian Liu Exponential-time and subexponential-time
sets . . . . . . . . . . . . . . . . . . 371--381
Steven Homer and
Stuart Kurtz and
James Royer On $1$-truth-table-hard languages . . . 383--389
Sándor Vágvölgyi A fast algorithm for constructing a tree
automaton recognizing a congruential
tree language . . . . . . . . . . . . . 391--399
S. Abiteboul and
P. Kanellakis Foreword . . . . . . . . . . . . . . . . 1
Ronald Fagin Finite-model theory --- a personal
perspective . . . . . . . . . . . . . . 3--31
Gabriel M. Kuper and
Moshe Y. Vardi On the complexity of queries in the
logical data model . . . . . . . . . . . 33--57
Catriel Beeri and
Yoram Kornatzky Algebraic optimization of
object-oriented query languages . . . . 59--94
Mariano P. Consens and
Alberto O. Mendelzon Low-complexity aggregation in GraphLog
and Datalog . . . . . . . . . . . . . . 95--116
Peter Z. Revesz A closed-form evaluation for Datalog
queries with integer (gap)-order
constraints . . . . . . . . . . . . . . 117--149
Ron van der Meyden Recursively indefinite databases . . . . 151--194
Richard J. Lipton and
Jeffrey F. Naughton and
Donovan A. Schneider and
S. Seshadri Efficient sampling strategies for
relational database operations . . . . . 195--226
A. Ehrenfeucht and
G. Rozenberg $T$-Structures, $T$-functions and texts 227--290
Beat Brüderlin Using geometric rewrite rules for
solving geometric problems symbolically 291--303
Juhani Karhumäki and
Wojciech Rytter and
Stefan Jarominek Efficient constructions of test sets for
regular and context-free languages . . . 305--316
Yannick Saouter and
Patrice Quinton Computability of recurrence equations 317--337
Mircea Andra\csiu and
Gheorghe P\uaun and
Jürgen Dassow and
Arto Salomaa Language-theoretic problems arising from
Richelieu cryptosystems . . . . . . . . 339--357
Esteban Feuerstein and
Alberto Marchetti-Spaccamela Dynamic algorithms for shortest paths in
planar graphs . . . . . . . . . . . . . 359--371
Karel Culik II and
Simant Dube Affine automata and related techniques
for generation of complex images . . . . 373--398
Elias Koutsoupias Improvements on Khrapchenko's theorem 399--403
Hans Kleine Büning On generalized Horn formulas and
$k$-resolution . . . . . . . . . . . . . 405--413
Pavel Pudlák and
Petr Savický On shifting networks (Boolean circuit) 415--419
Burkhard Monien and
Wojciech Rytter and
Leopold Schäpers Fast recognition of deterministic CFL's
with a smaller number of processors . . 421--429
Anonymous Conference on Formal Power Series and
Algebraic Combinatorics . . . . . . . . ??
M. Delest and
G. Jacob and
P. Leroux Forward . . . . . . . . . . . . . . . . 1
Gilbert Labelle Sur la symétrie et l'asymétrie des
structures combinatoires. (French) [On
the symmetry and asymmetry of
combinatorial structures] . . . . . . . 3--22
Doron Zeilberger Identities in search of identity . . . . 23--38
Marcella Anselmo The operation $\uparrow$ on formal power
series . . . . . . . . . . . . . . . . . 39--43
Didier Arques and
Isabelle Jacques Classification des cartes pointées de
genre $1$ et relation fonctionnelle
associée. (French) [Classification of
genus-$1$ pointed maps and associated
functional relation] . . . . . . . . . . 45--65
J. Bétréma and
J. G. Penaud Animaux et arbres guingois. (French)
[Animals and lop-sided trees] . . . . . 67--89
Anders Björner The Möbius function of factor order . . . 91--98
R. Casas and
J. Díaz and
C. Martínez Average-case analysis on simple families
of trees using a balanced probability
model . . . . . . . . . . . . . . . . . 99--112
William Y. C. Chen Context-free grammars, differential
operators and formal power series . . . 113--130
Yves Chiricota Représentation symbolique d'esp\`eces
moléculaires. (French) [Symbolic
representation of molecular species] . . 131--136
Seul Hee Choi and
Dominique Gouyou-Beauchamps Enumeration of generalized Young
tableaux with bounded height . . . . . . 137--151
I. Constantineau Auto-similarité dans la combinatoire des
polynômes orthogonaux. (French)
[Auto-similarity in the combination of
orthogonal polynomials] . . . . . . . . 153--167
Hél\`ene Décoste Séries indicatrices et $q$-séries.
(French) [Indicator series and
$q$-series] . . . . . . . . . . . . . . 169--186
S. Dulucq and
S. Gire Complexité d'algorithmes et opérations sur
les arbres. (French) [Algorithmic
complexity and operations on trees] . . 187--198
Shalosh B. Ekhad A short, elementary, and easy, WZ proof
of the Askey-Gasper inequality that was
used by de Branges in his proof of the
Bieberbach conjecture . . . . . . . . . 199--202
J. C. Lalanne Sur une involution sur les chemins de
Dyck. (French) [On an involution on Dyck
paths] . . . . . . . . . . . . . . . . . 203--215
Pierre Lalonde Bases de Lyndon des alg\`ebres de Lie
libres partiellement commutatives.
(French) [Lyndon bases for partially
commutative free Lie algebras] . . . . . 217--226
S. K. Lando and
A. K. Zvonkin Plane and projective meanders . . . . . 227--241
Roberto Mantaci Sur la distribution des anti-excédances
dans le groupe symétrique et dans ses
sousgroupes. (French) [On the
anti-exceedance distribution in a
symmetrical group in its sub-groups] . . 243--253
Guy Melançon Constructions des bases standard des
$K<A>$-modules \`a droite. (French)
[Construction of standard bases for
right $K<A>$-modules] . . . . . . . . . . 255--272
Bruce E. Sagan Combinatorial proofs of hook generating
functions for skew plane partitions . . 273--287
Dragutin Svrtan New plethysm operation, Chern characters
of exterior and symmetric powers with
applications to Stiefel-Whitney classes
of Grassmannians . . . . . . . . . . . . 289--301
Julian West Sorting twice through a stack . . . . . 303--313
B. Rovan Introduction . . . . . . . . . . . . . . 1
Sanjoy K. Baruah and
Rodney R. Howell and
Louis E. Rosier Feasibility problems for recurring tasks
on one processor . . . . . . . . . . . . 3--20
Philippe Darondeau and
Pierpaolo Degano Refinement of actions in event
structures and causal trees . . . . . . 21--48
Viliam Geffert A speed-up theorem without tape
compression . . . . . . . . . . . . . . 49--65
Igor Walukiewicz Gentzen-type axiomatization for PAL . . 67--79
Ingo Wegener BOTTOM-UP-HEAP\-SORT, a new variant of
HEAP\-SORT, beating, on an average,
QUICK\-SORT (if $n$ is not very small) 81--98
Pierre Deransart Proof methods of declarative properties
of definite programs . . . . . . . . . . 99--166
Hubert Comon Complete axiomatizations of some
quotient term algebras . . . . . . . . . 167--191
Iain A. Stewart Methods for proving completeness via
logical reductions . . . . . . . . . . . 193--229
M. Draghicescu and
S. Purushothaman A uniform treatment of order of
evaluation and aggregate update . . . . 231--262
Jan Friso Groote Transition system specifications with
negative premises . . . . . . . . . . . 263--299
Alex K. Simpson A characterisation of the
least-fixed-point operator by
dinaturality . . . . . . . . . . . . . . 301--314
Thomas Eiter and
Georg Gottlob Erratum: Propositional circumscription
and extended closed-world reasoning are
$\Pi^P_2$-complete . . . . . . . . . . . 315--315
Anonymous 5th Soviet --- French Symposium on
Theoretical Computer Science, Methods
and Tools for Compilation, and Program
Development (Informatika '91) . . . . . ??
Kablan Barbar Attributed tree grammars . . . . . . . . 3--22
M.-M. Corsini and
K. Musumbu Type inference in Prolog: a new approach 23--38
Philippe Devienne and
Patrick Leb\`egue and
Max Dauchet Weighted systems of equations . . . . . 39--62
A. Ja. Dikovsky On computational complexity of Prolog
programs . . . . . . . . . . . . . . . . 63--102
Walter Dosch On a generalized product for domains . . 103--125
Zineb Habbas A complete modal proof system for HAL:
the Herbrand agent language . . . . . . 127--143
A. A. Letichevsky and
J. V. Kapitonova and
S. V. Konozenko Computations in APS (algebraic
programming system) . . . . . . . . . . 145--171
V. A. Nepomniaschy and
A. A. Sulimov Problem-oriented verification system and
its application to linear algebra
programs . . . . . . . . . . . . . . . . 173--185
Vladimir Yu Sazonov Hereditarily-finite sets, data bases and
polynomial-time computability . . . . . 187--214
A. O. Slissenko On fault tolerance of syntax . . . . . . 215--222
M. K. Valiev $P^1_1$-universality of some
propositional logics of concurrent
programs . . . . . . . . . . . . . . . . 223--232
Miroslaw Kutylowski Stack versus sensitivity for one-way
automata . . . . . . . . . . . . . . . . 233--245
Alberto Apostolico and
Andrzej Ehrenfeucht Efficient detection of
quasiperiodicities in strings . . . . . 247--265
Jean-Camille Birget Partial orders on words, minimal
elements of regular languages, and state
complexity . . . . . . . . . . . . . . . 267--291
Marius Zimand If not empty, NP-P is topologically
large . . . . . . . . . . . . . . . . . 293--310
Walter Stromquist and
Daniel Ullman Sequential compounds of combinatorial
games . . . . . . . . . . . . . . . . . 311--321
David Wolfe Snakes in Domineering games . . . . . . 323--329
Roberto Tamassia and
Ioannis G. Tollis Dynamic reachability in planar digraphs
with one source and one sink . . . . . . 331--343
B. Litow and
Ph. Dumas Additive cellular automata and algebraic
series . . . . . . . . . . . . . . . . . 345--354
B. John Oommen and
David T. H. Ng An optimal absorbing list organization
strategy with constant memory
requirements . . . . . . . . . . . . . . 355--361
Tao Jiang and
Ming Li On the complexity of learning strings
and sequences . . . . . . . . . . . . . 363--371
E. Knill and
P. T. Cox and
T. Pietrzykowski Equality and abductive residua for Horn
clauses . . . . . . . . . . . . . . . . 1--44
G. Nota and
S. Orefice and
G. Pacini and
F. Ruggiero and
G. Tortora Legality concepts for three-valued logic
programs . . . . . . . . . . . . . . . . 45--68
Michal Grabowski On the status of proving program
properties in effective interpretations 69--81
Stefano Baratella A class of programs for which SLDNF
resolution and NAF rule are complete . . 83--99
Paul Gastin and
Brigitte Rozoy The poset of infinitary traces . . . . . 101--121
P. Cousot and
R. Cousot ``A la Burstall'' intermittent
assertions induction principles for
proving inevitability properties of
programs . . . . . . . . . . . . . . . . 123--155
Wenhui Zhang Cut formulas in propositional logic . . 157--168
Yves Marcoux Composition is almost (but not quite) as
good as $s-1-1$ . . . . . . . . . . . . 169--195
Anne Brüggemann-Klein Regular expressions into finite automata 197--213
Gen-Huey H. Chen and
Biing-Feng F. Wang and
Hungwen Li Deriving algorithms on reconfigurable
networks based on function decomposition 215--227
Juha Honkala On D$0$L systems with immigration . . . 229--245
Changwook Kim and
Dong Hoon Lee Separating $k$-separated eNCE graph
languages . . . . . . . . . . . . . . . 247--259
Rajanarayanan Subbiah and
Sitharama S. Iyengar and
Sridhar Radhakrishnan and
R. L. Kashyap An optimal distributed algorithm for
recognizing mesh-connected networks . . 261--278
Bin Fu and
Hong-zhou Li On symmetric differences of NP-hard sets
with weakly P-selective sets . . . . . . 279--291
Gheorghe P\uaun and
Arto Salomaa Closure properties of slender languages 293--301
Klaas Sikkel Parallel on-line parsing in constant
time per word . . . . . . . . . . . . . 303--310
A. Ferreira On space-efficient algorithms for
certain NP-complete problems . . . . . . 311--315
M. Abadi and
L. Cardelli and
P.-L Curien A short scientific biography of Corrado
Bohm . . . . . . . . . . . . . . . . . . 1
M. Abadi and
L. Cardelli and
P.-L. Curien Formal parametric polymorphism . . . . . 9--58
Henk Barendregt Constructive proofs of the range
property in lambda calculus . . . . . . 59--69
Alessandro Berarducci and
Benedetto Intrigila Some new results on easy lambda-terms 71--88
Robert L. Constable and
Scott F. Smith Computational foundations of basic
recursive function theory . . . . . . . 89--112
Mario Coppo and
Alberto Ferrari Type inference, abstract interpretation
and strictness analysis . . . . . . . . 113--143
Gérard Huet An analysis of Böhm's theorem . . . . . . 145--167
G. Jacopini and
G. Sontacchi General recursive functions in a very
simply interpretable typed
$\lambda$-calculus . . . . . . . . . . . 169--178
Stephen Brookes Historical introduction to ``Concrete
domains'' by G. Kahn and G. D. Plotkin 179--186
G. Kahn and
G. D. Plotkin Concrete domains (programming languages
semantics) . . . . . . . . . . . . . . . 187--277
Jan Willem Klop and
Vincent van Oostrom and
Femke van Raamsdonk Combinatory reduction systems:
introduction and survey . . . . . . . . 279--308
Daniel Leivant Functions over free algebras definable
in the simply typed lambda calculus . . 309--321
Giuseppe Longo and
Kathleen Milsted and
Sergei Soloviev The genericity theorem and parametricity
in the polymorphic $\lambda$-calculus 323--349
Gordon D. Plotkin Set-theoretical and other elementary
models of the $\lambda$-calculus . . . . 351--409
Dana S. Scott A type-theoretical alternative to ISWIM,
CUCH, OWHY . . . . . . . . . . . . . . . 411--440
Rick Statman Some examples of non-existent
combinators . . . . . . . . . . . . . . 441--448
S. Goto and
K. Satoh Preface to the Special Issue of Selected
Papers of the Fifth Generation Computer
Systems Conference, Tokyo, June 1--5,
1992 . . . . . . . . . . . . . . . . . . 1
A. Bossi and
M. Gabbrielli and
G. Levi and
M. C. Meo A compositional semantics for logic
programs . . . . . . . . . . . . . . . . 3--47
Luís Moniz Pereira and
José J. Alferes and
Joaquim N. Aparício Adding closed world assumptions to
well-founded semantics . . . . . . . . . 49--68
Tadashi Kawamura Logic program synthesis from first-order
logic specifications . . . . . . . . . . 69--96
Bern Martens and
Danny De Schreye and
Tamás Horváth Sound and complete partial deduction
with unfolding based on well-founded
measures . . . . . . . . . . . . . . . . 97--117
Makoto Tatsuta Realizability interpretation of
coinductive definitions and program
synthesis with streams . . . . . . . . . 119--136
Yukihide Takayama Defining concurrent processes
constructively . . . . . . . . . . . . . 137--164
Andrea Corradini and
Ugo Montanari and
Francesca Rossi An abstract machine for concurrent
modular systems: CHARM . . . . . . . . . 165--200
V. Poirriez MLOG: a strongly typed confluent
functional language with logical
variables . . . . . . . . . . . . . . . 201--223
Marc Denecker and
Danny De Schreye On the duality of abduction and model
generation in a framework for model
generation with equality . . . . . . . . 225--262
Hassan A\"\it-Kaci and
Andreas Podelski and
Gert Smolka A feature constraint system for logic
programming with entailment . . . . . . 263--283
Anonymous 10th `Journées Mathématiques-Informatique'
(Mathematics --- Computer Science) . . . ??
Jean-Paul Allouche Note on the cyclic Towers of Hanoi . . . 3--7
Marc Roland Assous and
Vincent Bouchitté and
Christine Charretton and
Brigitte Rozoy Finite labelling problem in event
structures . . . . . . . . . . . . . . . 9--19
A. Bertrand Sur une conjecture d'Yves Métivier.
(French) [On a conjecture of Yves
Métivier (rewriting system)] . . . . . . 21--30
Claude Bertrand A natural semantics of first-order type
dependency . . . . . . . . . . . . . . . 31--53
F. Blanchard and
S. Fabre Quelques procédés engendrant des suites
infinies. (French) [Some production
procedures of infinite sequences] . . . 55--60
Jean-Pierre Borel Symbolic representation of piecewise
linear functions on the unit interval
and application to discrepancy . . . . . 61--87
Claude Chaunier and
Nik Lygero\=s Le nombre de posets \`a isomorphie
pr\`es ayant $12$ éléments. (French) [The
number of nearly isomorphic posets
having $12$ elements] . . . . . . . . . 89--94
Hervé Daudé and
Brigitte Vallée An upper bound on the average number of
iterations of the LLL algorithm . . . . 95--115
Dominique Duval and
Pascale Sénéchaud Sketches and parametrization . . . . . . 117--130
Henri Faure Multidimensional quasi Monte-Carlo
methods . . . . . . . . . . . . . . . . 131--137
Zbigniew S. Kowalski Multiple returns under a bounded number
of iterations . . . . . . . . . . . . . 139--144
M. Mignotte Sur l'équation de Catalan. II. (French)
[On Catalan's equation. II (number
theory)] . . . . . . . . . . . . . . . . 145--149
Eric Rémila A linear algorithm to tile the trapezes
with $h_m$ and $v_n$ . . . . . . . . . . 151--165
Xiangdong Ye Coexistence of uniquely ergodic
subsystems of interval mapping . . . . . 167--181
Dung T. Huynh and
Lu Tian Deciding bisimilarity of normed
context-free processes is in
$\Sigma^p_2$ . . . . . . . . . . . . . . 183--197
Bruno Martin A universal cellular automaton in
quasi-linear time and its S--m--n form 199--237
F. Blanchet-Sadri Equations and monoid varieties of
dot-depth one and two . . . . . . . . . 239--258
M. Clerbout and
D. Gonzalez Atomic semicommutations . . . . . . . . 259--272
Jean-Camille Birget and
Stuart W. Margolis and
John C. Meakin The word problem for inverse monoids
presented by one idempotent relator . . 273--289
Philippe Flajolet and
Peter Grabner and
Peter Kirschenhofer and
Helmut Prodinger and
Robert F. Tichy Mellin transforms and asymptotics:
digital sums . . . . . . . . . . . . . . 291--314
Kunimasa Aoki and
Juichi Shinoda and
Teruko Tsuda On $\Pi_2$ theories of hp-$T$ degrees of
low sets . . . . . . . . . . . . . . . . 315--327
Shigeki Iwata and
Takumi Kasai The Othello game on an $n \times n$
board is PSPACE-complete . . . . . . . . 329--340
Daniel Mey Finite games for a predicate logic
without contractions . . . . . . . . . . 341--349
Grahame Bennett Double dipping: the case of the missing
binomial coefficient identities . . . . 351--375
Dexter Kozen and
Shmuel Zaks Optimal bounds for the change-making
problem . . . . . . . . . . . . . . . . 377--388
Maria M. Klawe Shallow grates . . . . . . . . . . . . . 389--395
S. Burckel Functional equations associated with
congruential functions . . . . . . . . . 397--406
Edith Hemaspaandra and
Lane A. Hemaspaandra Quasi-injective reductions . . . . . . . 407--413
Naomi Nishimura Restricted CRCW PRAMs . . . . . . . . . 415--426
Burkhard Monien and
Wojciech Rytter and
Helmut Schäpers Fast recognition of deterministic CFL's
with a smaller number of processors
(corrigendum) . . . . . . . . . . . . . 427--428
M. E. Majster-Cederbaum and
F. Zetzsche The comparison of a cpo-based semantics
with a cms-based semantics for CSP . . . 1--40
Béatrice Bérard Global serializability of concurrent
programs . . . . . . . . . . . . . . . . 41--70
Susumu Yamasaki A denotational semantics and dataflow
construction for logic programs . . . . 71--91
Michael Codish and
Dennis Dams and
Eyal Yardeni Bottom-up abstract interpretation of
logic programs . . . . . . . . . . . . . 93--125
Satish R. Thatte Type inference with partial types . . . 127--148
J. A. Bergstra and
J. Heering Which data types have omega-complete
initial algebra specifications? . . . . 149--168
Ursula Goltz and
Arend Rensink Finite Petri nets as models for
recursive causal behaviour . . . . . . . 169--179
Kees Doets Left termination turned into termination 180--187
Michael Barr Additions and corrections to ``Terminal
coalgebras in well-founded set theory'' 189--192
Andrew M. Pitts A co-induction principle for recursively
defined domains . . . . . . . . . . . . 195--219
Malika More Investigation of binary spectra by
explicit polynomial transformations of
graphs . . . . . . . . . . . . . . . . . 221--272
Wim H. Hesselink Nondeterminacy and recursion via stacks
and games . . . . . . . . . . . . . . . 273--295
A. Bossi and
N. Cocco and
M. Fabris Norms on terms and their use in proving
universal termination of a logic program 297--328
Jung-Heum Park and
Kyung-Yong Chwa On the construction of regular minimal
broadcast digraphs . . . . . . . . . . . 329--342
Jean-Jacques Hébrard A linear algorithm for renaming a set of
clauses as a Horn set . . . . . . . . . 343--350
I. Mitrani and
E. Gelenbe Preface . . . . . . . . . . . . . . . . 1
E. G. Coffman, Jr. and
Leopold Flatto and
Bjorn Poonen and
Paul E. Wright The processor minimization problem with
independent waiting-time constraints . . 3--16
M. B. Combé and
O. J. Boxma Optimization of static traffic
allocation policies . . . . . . . . . . 17--43
Graham Louth and
Michael Mitzenmacher and
Frank Kelly Computational complexity of loss
networks . . . . . . . . . . . . . . . . 45--59
Micha Hofri and
Yaakov Kogan Asymptotic analysis of product-form
distributions related to large
interconnection networks . . . . . . . . 61--90
Ram Chakka and
Isi Mitrani Heterogeneous multiprocessor systems
with breakdowns: Performance and optimal
repair strategies . . . . . . . . . . . 91--109
Ian F. Akyildiz and
Horst von Brand Exact solutions for networks of queues
with blocking-after-service . . . . . . 111--130
Erol Gelenbe and
Marisela Hernández Virus tests to maximize availability of
software systems . . . . . . . . . . . . 131--147
François Baccelli and
William A. Massey and
Paul E. Wright Determining the exit time distribution
for a closed cyclic network . . . . . . 149--165
Paul Gastin and
Antoine Petit and
Wieslaw Zielonka An extension of Kleene's and Ochmanski's
theorems to infinite traces . . . . . . 167--204
Martin Middendorf More on the complexity of common
superstring and supersequence problems 205--228
Mody Lempel and
Azaria Paz An algorithm for finding a shortest
vector in a two-dimensional modular
lattice . . . . . . . . . . . . . . . . 229--241
Tao Jiang and
Oscar H. Ibarra and
Hui Wang Some results concerning 2-D on-line
tessellation acceptors and 2-D
alternating finite automata . . . . . . 243--257
A. Ehrenfeucht and
P. Ten Pas and
G. Rozenberg Properties of grammatical codes of trees 259--293
Marty J. Wolf Nondeterministic circuits, space
complexity and quasigroups . . . . . . . 295--313
Sheng Yu and
Qingyu Zhuang and
Kai Salomaa The state complexities of some basic
operations on regular languages . . . . 315--328
Eric Goles Lyapunov operators to study the
convergence of extremal automata . . . . 329--337
B. Litow A context-free language decision problem 339--343
Vineet Bafna and
Bala Kalyanasundaram and
Kirk Pruhs Not all insertion methods yield constant
approximate tours in the Euclidean plane 345--353
Robert E. Matthews An inherently iterative algorithm for
the Grzegorczyk hierarchy . . . . . . . 355--360
Alexandru Mateescu Scattered deletion and commutativity . . 361--371
Pengyuan Chen The communication complexity of
computing differentiable functions in a
multicomputer network . . . . . . . . . 373--383
J.-C Raoult Preface . . . . . . . . . . . . . . . . 1
Henrik Reif Andersen Model checking and Boolean graphs . . . 3--30
Anne-Cécile Caron and
Jean-Luc Coquide Decidability of reachability for
disjoint union of term rewriting systems 31--52
Bruno Courcelle Monadic second-order definable graph
transductions: a survey . . . . . . . . 53--75
Mads Dam CTL$*$ and ECTL$*$ as fragments of the
modal $\mu$-calculus . . . . . . . . . . 77--96
Andreas Potthoff Modulo-counting quantifiers over finite
trees . . . . . . . . . . . . . . . . . 97--112
Helmut Seidl Finite tree automata with cost functions 113--142
Doron Peled and
Amir Pnueli Proving partial order properties . . . . 143--182
Rajeev Alur and
David L. Dill A theory of timed automata . . . . . . . 183--235
J. A. Gerhard and
Mario Petrich Unification in free distributive
lattices . . . . . . . . . . . . . . . . 237--257
Vincent van Oostrom Confluence by decreasing diagrams . . . 259--280
Laurent Regnier Une equivalence sur les lambda-termes.
(French) [Equivalence between
lambda-terms] . . . . . . . . . . . . . 281--292
C. Hosono and
Y. Ikeda A formal derivation of the decidability
of the theory SA . . . . . . . . . . . . 1--23
Kai Salomaa Synchronized tree automata . . . . . . . 25--51
J. W. Daykin and
C. S. Iliopoulos and
W. F. Smyth Parallel RAM algorithms for factorizing
words . . . . . . . . . . . . . . . . . 53--67
Jean-Luc Coquidé and
Max Dauchet and
Rémi Gilleron and
Sándor Vágvölgyi Bottom-up tree pushdown automata:
classification and connection with
rewrite systems . . . . . . . . . . . . 69--98
B. Codenotti and
M. Leoncini and
G. Resta Oracle computations in parallel
numerical linear algebra . . . . . . . . 99--121
Juraj Hromkovi\vc and
Jarkko Kari and
Lila Kari Some hierarchies for the communication
complexity measures of cooperating
grammar systems . . . . . . . . . . . . 123--147
M. Jantzen and
H. Petersen Cancellation in context-free languages:
enrichment by reduction . . . . . . . . 149--170
Katsushi Inoue and
Akira Ito and
Itsuo Takanami On $1$-inkdot alternating Turing
machines with small space . . . . . . . 171--179
Sergio De Agostino P-complete problems in data compression 181--186
A. Del Lungo Polyominoes defined by two vectors . . . 187--198
Helen Cameron and
Derick Wood Balance in AVL trees and space cost of
brother trees . . . . . . . . . . . . . 199--228
Jarkko Kari Rice's theorem for the limit sets of
cellular automata . . . . . . . . . . . 229--254
Samir Khuller and
Stephen G. Mitchell and
Vijay V. Vazirani On-line algorithms for weighted
bipartite matching and stable marriages 255--267
Juha Honkala On generalized DT$0$L systems and their
fixed points . . . . . . . . . . . . . . 269--286
Armando B. Matos Periodic sets of integers . . . . . . . 287--312
J. B. Yun\`es Seven-state solutions to the Firing
Squad Synchronization Problem . . . . . 313--332
E. Barcucci and
R. Pinzani and
R. Sprugnoli The random generation of directed
animals . . . . . . . . . . . . . . . . 333--350
Sanjay Jain and
Arun Sharma Program size restrictions in
computational learning . . . . . . . . . 351--386
A. H. Deutz and
A. Ehrenfeucht and
G. Rozenberg Hyperedge channels are abelian . . . . . 387--393
Juraj Hromkovi\vc and
Claus-Dieter Jeschke and
Burkhard Monien Note on optimal gossiping in some
weak-connected graphs . . . . . . . . . 395--402
Yonatan Aumann and
Michael O. Rabin Clock construction in fully asynchronous
parallel systems and PRAM simulation . . 3--30
Tom Leighton Methods for message routing in parallel
machines . . . . . . . . . . . . . . . . 31--62
J. Garofalakis and
P. Spirakis and
B. Tampakas and
S. Rajsbaum Tentative and definite distributed
computations: an optimistic approach to
network synchronization . . . . . . . . 63--74
Gilad Koren and
Dennis Shasha MOCA: a multiprocessor on-line
competitive algorithm for real-time
system scheduling . . . . . . . . . . . 75--97
Doron Peled and
Mathai Joseph A compositional framework for fault
tolerance by specification
transformation . . . . . . . . . . . . . 99--125
Henk Schepers and
Jozef Hooman A trace-based compositional proof theory
for fault tolerant distributed systems 127--157
Padmanabhan Krishnan A semantic characterisation for faults
in replicated systems . . . . . . . . . 159--177
Hermann de Meer and
Kishor S. Trivedi and
Mario Dal Cin Guarded repair of dependable systems . . 179--210
Vinay Sadananda Pai and
Alejandro A. Schäffer and
Peter J. Varman Markov analysis of multiple-disk
prefetching strategies for external
merging . . . . . . . . . . . . . . . . 211--239
Jehoshua Bruck and
Robert Cypher and
Ching-Tien Ho Tolerating faults in a mesh with a row
of spare nodes . . . . . . . . . . . . . 241--252
Uri Abraham and
Menachem Magidor On the mutual-exclusion problem --- a
quest for minimal solutions . . . . . . 1--38
Hirofumi Yokouchi $F$-semantics for type assignment
systems . . . . . . . . . . . . . . . . 39--77
Jean-Louis L. Krivine A general storage theorem for integers
in call-by-name $\lambda$-calculus . . . 79--94
Cheng-Chia Chen and
I-Peng Lin The computational complexity of the
satisfiability of modal Horn clauses for
modal propositional logics . . . . . . . 95--121
Jiawang Wei Correctness of fixpoint transformations 123--142
J. C. Shepherdson The role of standardising apart in logic
programming . . . . . . . . . . . . . . 143--166
Zoran Ognjanovi\'c A tableau-like proof procedure for
normal modal logics . . . . . . . . . . 167--186
R. Banach Regular relations and bicartesian
squares . . . . . . . . . . . . . . . . 187--192
Wenhui Zhang Depth of proofs, depth of cut-formulas
and complexity of cut formulas . . . . . 193--206
A. H. Deutz and
A. Ehrenfeucht and
G. Rozenberg Clans and regions in $2$-structures . . 207--262
Jean-Paul Allouche and
Mireille Bousquet-Mélou Canonical positions for the factors in
paperfolding sequences . . . . . . . . . 263--278
Bernard Delyon and
Oded Maler On the effects of noise and speed on
computations . . . . . . . . . . . . . . 279--291
Joseph F. Jájá and
Kwan Woo Ryu An efficient parallel algorithm for the
single function coarsest partition
problem . . . . . . . . . . . . . . . . 293--307
K. Ganesan One-way functions and the isomorphism
conjecture . . . . . . . . . . . . . . . 309--321
Craig A. Rich and
Giora Slutzki The complexity of optimizing
finite-state transducers . . . . . . . . 323--336
Timo Knuutila and
Magnus Steinby The inference of tree languages from
finite samples: an algebraic approach 337--367
S. Ferenczi Tiling and local rank properties of the
Morse sequence . . . . . . . . . . . . . 369--383
Marion Scheepers Variations on a game of Gale (II):
Markov strategies . . . . . . . . . . . 385--396
D. M. Yellin An algorithm for dynamic subset and
intersection testing . . . . . . . . . . 397--406
Ömer E\vgecio\vglu and
Çetin Kaya Koç Exponentiation using canonical recoding 407--417
M. Margenstern Nonerasing Turing machines: a frontier
between a decidable halting problem and
universality . . . . . . . . . . . . . . 419--424
Gerhard J. Woeginger On-line scheduling of jobs with fixed
start and end times . . . . . . . . . . 5--16
Rajeev Motwani and
Steven Phillips and
Eric Torng Nonclairvoyant scheduling . . . . . . . 17--47
Anja Feldmann and
Ji\vrí Sgall and
Shang-Hua Teng Dynamic scheduling on parallel machines 49--72
Yossi Azar and
Andrei Z. Broder and
Anna R. Karlin On-line load balancing . . . . . . . . . 73--84
Amos Fiat and
Moty Ricklin Competitive algorithms for the weighted
server problem . . . . . . . . . . . . . 85--99
Fabrizio d'Amore and
Vincenzo Liberatore The list update problem and the
retrieval of sets . . . . . . . . . . . 101--123
Bala Kalyanasundaram and
Kirk R. Pruhs Constructing competitive tours from
local information . . . . . . . . . . . 125--138
John Hershberger and
Monika Rauch and
Subhash Suri Data structures for two-edge
connectivity in planar graphs . . . . . 139--161
Magnus M. Halldórsson and
Mario Szegedy Lower bounds for on-line graph coloring 163--174
Noga Alon and
Gil Kalai and
Moty Ricklin and
Larry Stockmeyer Lower bounds on the competitive ratio
for mobile user tracking and distributed
job scheduling . . . . . . . . . . . . . 175--201
Peter Bro Miltersen and
Sairam Subramanian and
Jeffrey Scott Vitter and
Roberto Tamassia Complexity models for incremental
computation . . . . . . . . . . . . . . 203--236
M. Nivat Gödel's incompleteness theorem, by V. A.
Uspensky . . . . . . . . . . . . . . . . 237
Vladimir A. Uspensky Gödel's incompleteness theorem . . . . . 239--319
Neil V. Murray and
Erik Rosenthal On the relative merits of path
dissolution and the method of analytic
tableaux . . . . . . . . . . . . . . . . 1--28
R. Banach Term graph rewriting and garbage
collection using opfibrations . . . . . 29--94
Kevin J. Compton Stratified least fixpoint logic . . . . 95--120
Satoshi Kobayashi and
Makoto Tatsuta Realizability interpretation of
generalized inductive definitions . . . 121--138
Limor Fix and
Nissim Francez and
Orna Grumberg Program composition via unification . . 139--179
Luca Aceto GSOS and finite labelled transition
systems . . . . . . . . . . . . . . . . 181--195
Philippe Mathieu and
Jean-Paul Delahaye A kind of logical compilation for
knowledge bases . . . . . . . . . . . . 197--218
David Scholefield and
Hussein Zedan and
He Jifeng A specification-oriented semantics for
the refinement of real-time systems . . 219--241
Yael Etzion-Petruschka and
David Harel and
Dale Myers On the solvability of domino snake
problems . . . . . . . . . . . . . . . . 243--269
Craig C. Squier and
Friedrich Otto and
Yuji Kobayashi A finiteness condition for rewriting
systems . . . . . . . . . . . . . . . . 271--294
Ramana M. Idury and
Alejandro A. Schäffer Dynamic dictionary matching with failure
functions . . . . . . . . . . . . . . . 295--310
Ernst L. Leiss Language equations over a one-letter
alphabet with union, concatenation and
star: a complete solution . . . . . . . 311--330
Hava T. Siegelmann and
Eduardo D. Sontag Analog computation via neural networks 331--360
Peter Eades and
Sue Whitesides Drawing graphs in two layers . . . . . . 361--374
Dani\`ele Gardy Join sizes, urn models, and normal
limiting distributions . . . . . . . . . 375--414
J. Spencer Randomization, derandomization and
antirandomization: three games . . . . . 415--429
K. Eriksson Reachability is decidable in the numbers
game . . . . . . . . . . . . . . . . . . 431--439
Dung T. Huynh and
Lu Tian A note on the complexity of deciding
bisimilarity of normed unary processes 441--448
A. Bergey and
R. Cori On the orbits of the product of two
permutations . . . . . . . . . . . . . . 449--461
C. Picouleau Complexity of the Hamiltonian cycle in
regular graph problem . . . . . . . . . 463--473
N. Anderson and
D. Manley A matrix extension of Winograd's inner
product algorithm . . . . . . . . . . . 475--477
Philippe Flajolet and
Paul Zimmerman and
Bernard Van Cutsem A calculus for the random generation of
labelled combinatorial structures . . . 1--35
David W. Juedes and
James I. Lathrop and
Jack H. Lutz Computational depth and reducibility . . 37--70
E. L. Leiss Unrestricted complementation in language
equations over a one-letter alphabet . . 71--84
Changwook Kim Retreat bounded picture languages . . . 85--112
Pascal Koiran and
Michel Cosnard and
Max Garzon Computability with low-dimensional
dynamical systems . . . . . . . . . . . 113--128
Lila Kari On language equations with invertible
operations . . . . . . . . . . . . . . . 129--150
Paola Bonizzoni Primitive $2$-structures with the
$(n-2)$-property . . . . . . . . . . . . 151--178
Giovanni Pighizzini Asynchronous automata versus
asynchronous cellular automata . . . . . 179--207
A. Ehrenfeucht and
R. McConnell A $k$-structure generalization of the
theory of $2$-structures . . . . . . . . 209--227
Klaus Ambos-Spies and
Steven Homer and
Robert I. Soare Minimal pairs and complete problems . . 229--241
Jean-Camille Birget and
Joseph B. Stephen Formal languages defined by uniform
substitutions . . . . . . . . . . . . . 243--258
Zsuzsanna Róka One-way cellular automata on Cayley
graphs . . . . . . . . . . . . . . . . . 259--290
Alfredo De Santis and
Giovanni Di Crescenzo and
Guiseppe Persiano The knowledge complexity of quadratic
residuosity languages . . . . . . . . . 291--317
Juraj Hromkovi\vc and
Branislav Rovan and
Anna Slobodova Deterministic versus nondeterministic
space in terms of synchronized
alternating machines . . . . . . . . . . 319--336
R. Diestel and
I. Leader Domination games on infinite graphs . . 337--345
Jefferey A. Shufelt and
Hans J. Berliner Generating Hamiltonian circuits without
backtracking from errors . . . . . . . . 347--375
Amir M. Ben-Amram Unit-cost pointers versus
logarithmic-cost addresses . . . . . . . 377--385
Douglas Bridges and
Cristian Calude On recursive bounds for the exceptional
values in speed-up . . . . . . . . . . . 387--394
Pierre Lescanne On termination of one rule rewrite
systems . . . . . . . . . . . . . . . . 395--401
Maxime Crochemore and
Wojciech Rytter On two-dimensional pattern matching by
optimal parallel algorithms . . . . . . 403--414
J. Berstel and
M. Pocchiola Average cost of Duval's algorithm for
generating Lyndon words . . . . . . . . 415--425
Lucian Ilie On a conjecture about slender
context-free languages . . . . . . . . . 427--434
Pavol \vDuri\vs and
José D. P. Rolim A note on the density of oracle
decreasing time-space complexity . . . . 435--444
Anonymous Workshop on Continuous Algorithms and
Complexity . . . . . . . . . . . . . . . ??
F. Cucker and
M. Shub and
S. Smale Separation of complexity classes in
Koiran's weak model . . . . . . . . . . 3--14
T. Emerson Relativizations of the P =? NP question
over the reals (and other ordered rings) 15--22
D. Yu. Grigoriev Deviation theorems for solutions of
differential equations and applications
to lower bounds on parallel complexity
of sigmoids . . . . . . . . . . . . . . 23--33
P. Koiran Computing over the reals with addition
and order (complexity theory) . . . . . 35--47
Petr K\ocircurka Regular unimodal systems and factors of
finite automata . . . . . . . . . . . . 49--64
Gregorio Malajovich On generalized Newton algorithms:
quadratic convergence, path-following
and error analysis . . . . . . . . . . . 65--84
K. Meer On the complexity of quadratic
programming in real number models of
computation . . . . . . . . . . . . . . 85--94
Christian Michaux P$\not=$NP over the nonstandard reals
implies P$\not=$NP over $R$ . . . . . . 95--104
J. Maurice Rojas A convex geometric approach to counting
the roots of a polynomial system . . . . 105--140
M. Shub and
S. Smale Complexity of Bezout's theorem V:
Polynomial time . . . . . . . . . . . . 141--164
Jan Verschelde and
Ann Haegemans Homotopies for solving polynomial
systems within a bounded domain . . . . 165--185
Anthony J. Bonner and
Michael Kifer An overview of transaction logic . . . . 205--265
Fangqing Dong and
Laks V. S. Lakshmanan Intuitionistic interpretation of
deductive databases with incomplete
information . . . . . . . . . . . . . . 267--306
D. Kapur and
X. Nie and
D. R. Musser An overview of the Tecton proof system 307--340
Geetha Ramanathan Refinement of events in the development
of real-time distributed systems . . . . 341--359
Jiawei Han Towards efficient induction mechanisms
in database systems . . . . . . . . . . 361--385
Robert Godin and
Rokia Missaoui An incremental concept formation
approach for learning from databases . . 387--419
Fereidoon Sadri Aggregate operations in the information
source tracking method . . . . . . . . . 421--442
Anonymous Second International Colloquium on
Words, Languages and Combinatorics . . . ??
J. A. Anderson Semiretracts of a free monoid . . . . . 3--11
Dani\`ele Beauquier and
Andreas Podelski Rabin tree automata and finite monoids 13--25
Agn\`es Bonnier-Rigny and
Daniel Krob A complete system of identities for
one-letter rational expressions with
multiplicities in the tropical semiring 27--50
Fernando Botelho and
Max Garzon Boolean neural nets are observable . . . 51--61
Renato M. Capocelli and
Luisa Gargano and
Ugo Vaccaro A fast algorithm for the unique
decipherability of multivalued encodings 63--78
Sini\vsa Crvenkovi\'c and
Rozália Sz Madarász On dynamic algebras . . . . . . . . . . 79--86
V. Diekert A partial trace semantics for Petri nets 87--105
H. Jürgensen and
K. Salomaa and
S. Yu Transducers and the decidability of
independence in free monoids . . . . . . 107--117
Alica Kelemenová and
Erzsébet Csuhaj-Varjú Languages of colonies . . . . . . . . . 119--130
Teo Mora An introduction to commutative and
non-commutative Gröbner bases . . . . . . 131--173
Friedrich Otto and
Paliath Narendran Codes modulo finite monadic
string-rewriting systems . . . . . . . . 175--188
Norman R. Reilly Bounds on the variety generated by
completely regular syntactic monoids
from finite prefix codes . . . . . . . . 189--208
J.-C. Spehner A bijection between cliques in graphs
and factorizations in free monoids . . . 209--223
Andreas Weber Finite-valued distance automata . . . . 225--251
Andreas Weber Exponential upper and lower bounds for
the order of a regular language . . . . 253--262
J. Köbler Locating P/poly optimally in the
extended low hierarchy . . . . . . . . . 263--285
Edward P. F. Chan Testing satisfiability of a class of
object-oriented conjunctive queries . . 287--309
Z. Fülöp Undecidable properties of deterministic
top-down tree transducers . . . . . . . 311--328
Michael Kaminski and
Nissim Francez Finite-memory automata . . . . . . . . . 329--363
Ferucio Laurentiu Tiplea and
Cristian Ene and
Cecilia Magdalena Ionescu and
Octavian Procopiuc Some decision problems for parallel
communicating grammar systems . . . . . 365--385
B. Durand Inversion of 2D cellular automata: some
complexity results . . . . . . . . . . . 387--401
T. Harju and
H. C. M. Kleijn and
M. Latteux and
A. Terlutte Representation of rational functions
with prefix and suffix codings . . . . . 403--413
Eric Remila On the tiling of a torus with two bars 415--426
Louis Mak Speedup of determinism by alternation
for multidimensional Turing machines . . 427--453
Franti\vsek Matú\vs Stochastic independence, algebraic
independence and abstract connectedness 455--471
Tao Jiang and
Ming Li Approximating shortest superstrings with
constraints . . . . . . . . . . . . . . 473--491
Elias Dahlhaus and
Marek Karpinski An efficient parallel algorithm for the
minimal elimination ordering (MEO) of an
arbitrary graph . . . . . . . . . . . . 493--528
Laurent Alonso Uniform generation of a Motzkin word . . 529--536
John Harrison Morphic congruences and D$0$L languages 537--544
Lance Fortnow and
John Rompel and
Michael Sipser On the power of multi-prover interactive
protocols . . . . . . . . . . . . . . . 545--557
Xunrang Gu and
Yuzhang Zhu Asymptotic optimal HEAPSORT algorithm 559--565
Anonymous Mathematical Foundations of Programming
Semantics . . . . . . . . . . . . . . . ??
Samson Abramsky Proofs as processes . . . . . . . . . . 5--9
G. Bellin and
P. J. Scott On the $\pi$-calculus and linear logic 11--65
Didier Galmiche and
Guy Perrier On proof normalization in linear logic 67--110
G. F. Mascari and
M. Pedicini Head linear reduction and pure proof net
extraction . . . . . . . . . . . . . . . 111--137
P. Lincoln and
A. Scedrov First-order linear logic without
modalities is NEXPTIME-hard . . . . . . 139--153
Patrick Lincoln and
Timothy Winkler Constant-only multiplicative linear
logic is NP-complete . . . . . . . . . . 155--169
Christel Baier and
Mila E. Majster-Cederbaum Denotational semantics in the cpo and
metric approach . . . . . . . . . . . . 171--220
Hartmut Ehrig and
Martin Große-Rhode Functorial theory of parameterized
specifications in a general
specification framework . . . . . . . . 221--266
Alexey L. Lastovetsky and
Sergey S. Gaissaryan An algebraic approach to semantics of
programming languages . . . . . . . . . 267--288
Felipe Bracho and
Manfred Droste Labelled domains and automata with
concurrency . . . . . . . . . . . . . . 289--318
Pascal Manoury and
Marianne Simonot Automatizing termination proofs of
recursively defined functions . . . . . 319--343
E. A. Scott Weights for total division orderings on
strings . . . . . . . . . . . . . . . . 345--359
Kunihiko Hiraishi Some complexity results on transition
systems and elementary net systems . . . 361--376
Jianan Li and
Ichiro Suzuki and
Masafumi Yamashita Fair Petri nets and structural induction
for rings of processes . . . . . . . . . 377--404
Peter Trigg and
J. Roger Hindley and
Martin W. Bunder Combinatory abstraction using $B$, $B'$
and friends . . . . . . . . . . . . . . 405--422
R. David The Inf function in the system $F$ . . . 423--431
P. T. Johnstone Variations on the bagdomain theme . . . 3--20
Reinhold Heckmann Stable power domains . . . . . . . . . . 21--56
Adrian Fiech and
Michael Huth Algebraic domains of natural
transformations . . . . . . . . . . . . 57--78
Austin Melton and
Bernd S. W. Schröder and
George E. Strecker Lagois connections --- a counterpart to
Galois connections . . . . . . . . . . . 79--107
Philip S. Mulry Partial map classifiers and partial
Cartesian closed categories . . . . . . 109--123
Eike Ritter Categorical abstract machines for
higher-order typed lambda --- calculi 125--162
Edmund Robinson Parametricity as isomorphism . . . . . . 163--181
Fairouz Kamareddine and
Rob Nederpelt A unified approach to type theory
through a refined lambda --- calculus 183--216
Roy L. Crole Computational adequacy of the FIX-logic 217--242
Bettina Blaaberg and
Christian Clausen Adequacy for a lazy functional language
with recursive and polymorphic types . . 243--275
D. A. Wolfram A semantics for $\lambda$Prolog . . . . 277--289
Eric Remila Recognition of graphs by automata . . . 291--332
Enno Ohlebusch On the modularity of termination of term
rewriting systems . . . . . . . . . . . 333--360
Aldo de Luca and
Filippo Mignosi Some combinatorial properties of
Sturmian words . . . . . . . . . . . . . 361--385
H. Senoussi and
A. Saoudi A quadtree algorithm for template
matching on a pyramid computer . . . . . 387--417
Vladimir Stetsenko On almost bad Boolean bases . . . . . . 419--469
M. Ito and
G. Thierrin Congruences, infix and cohesive prefix
codes . . . . . . . . . . . . . . . . . 471--485
Elvira Mayordomo Almost every set in exponential time is
P-bi-immune . . . . . . . . . . . . . . 487--506
Marek Chrobak and
Wojciech Rytter Two results on linear embeddings of
complete binary trees . . . . . . . . . 507--526
M. A. Kiwi and
R. Ndoundam and
M. Tchuente and
E. Goles No polynomial bound for the period of
the parallel chip firing game on graphs 527--532
H. Petersen A remark on a paper by A. B. Matos . . . 329--330
Fernanda Botelho and
Max Garzon Erratum to ``Boolean neural nets are
observable'' [Theoret. Comput. Sci. 134
(1994) 51--61] . . . . . . . . . . . . . 257--257
Guy Perrier Corrigendum to Galmiche's and Perrier's
``On proof normalization in linear
logic'' [Theoret. Comput. Sci 135(1)
(1994) 67--110] . . . . . . . . . . . . 353--354
Sergio De Agostino Erratum to ``P-complete Problems in Data
Compression'' [Theoret. Comput. Sci. 127
(1994) 181--186] . . . . . . . . . . . . 325--326