Last update: Wed Sep 26 08:25:52 MDT 2018
Volume 35, Number 1, January, 1985K.-J. Lange and E. Welzl Recurrent words and simultaneous growth in T0L systems . . . . . . . . . . . . . 1--15 J. Stern Characterizations of some classes of regular events . . . . . . . . . . . . . 17--42 S. L. Bloom and D. R. Troeger A logical characterization of observation equivalence . . . . . . . . 43--53 H. Edelsbrunner Finding transversals for sets of simple geometric figures . . . . . . . . . . . 55--69 Y. Metivier Calculation of the length of rewriting chains in free monoide . . . . . . . . . 71--87 C. Benoit Axiomatisation of tests . . . . . . . . 89--107 D. Kapur and M. S. Krishnamoorthy and R. McNaughton and Narendran and P. An $O(\bmod {T} \bmod ^3)$ algorithm for testing the Church--Rosser property of Thue systems . . . . . . . . . . . . . . 109--114 J.-P. Pecuchet Two-way finite automata and finite words 115--122
L. Fribourg A superposition oriented theorem prover 129--164 G. Ausiello and A. d'Atri and M. Moscarini On the existence of acyclic views in a database scheme . . . . . . . . . . . . 165--177 R. Cori and Y. Metivier Recognizable subsets of some partially Abelian monoids . . . . . . . . . . . . 179--189 G. Memmi and A. Finkel An introduction to FIFO nets-monogeneous nets: a subclass of FIFO nets . . . . . 191--214 K. Kobayashi On proving time constructibility of functions . . . . . . . . . . . . . . . 215--225 P. Narendran and F. Otto Complexity results on the conjugacy problem for monoids . . . . . . . . . . 227--243 D. A. Plaisted Complete divisibility problems for slowly utilized oracles . . . . . . . . 245--260 S. Hirose and S. Okawa and M. Yoneda A homomorphic characterization of recursively enumerable languages . . . . 261--269 J.-E. Pin and J. Sakarovitch An application of the matrix representation of transductions . . . . 271--293 T. Head and J. Wilkinson Code properties and homomorphisms of D0L systems . . . . . . . . . . . . . . . . 295--312 E. Leiss On classes of tractable unrestricted regular expressions . . . . . . . . . . 313--327 M. Oyamaguchi On the data type extension problem for algebraic specifications . . . . . . . . 329--336 D. Kapur and P. Narendran A finite Thue system with decidable word problem and without equivalent finite canonical system . . . . . . . . . . . . 337--344 I. Sain A simple proof for the completeness of Floyd's method . . . . . . . . . . . . . 345--348
M. Broy On the Herbrand-Kleene universe for nondeterministic computations . . . . . 1--19 J. Engelfriet Determinacy to (observation equivalence=trace equivalence) . . . . . 21--25 R. Janicki Transforming sequential systems into concurrent systems . . . . . . . . . . . 27--58 N. Blum An $\Omega(n^4/3)$ lower bound on the monotone network complexity of the $n^{th}$ degree convolution . . . . . . 59--69 M. L. Tiomkin and J. A. Makowsky Propositional dynamic logic with local assignments . . . . . . . . . . . . . . 71--87 Y. Igarashi A pumping lemma for real-time deterministic context-free languages . . 89--97 C. De Felice Construction of factorisation codes . . 99--108 S. Hirose and M. Yoneda On the Chomsky and Stanley's homomorphic characterization of context-free languages . . . . . . . . . . . . . . . 109--112 K. Ruohonen On equality of multiplicity sets of regular languages . . . . . . . . . . . 113--117 B. Scarpellini Complex Boolean networks obtained by diagonalization . . . . . . . . . . . . 119--125 G. Winskel On powerdomains and modality . . . . . . 127--137
N. E. Fenton and R. W. Whitty and A. A. Kaposi A generalised mathematical theory of structured programming . . . . . . . . . 145--171 I. H. Sudborough and E. Welzl Complexity and decidability for chain code picture languages . . . . . . . . . 173--202 J. Demel and M. Demlova and V. Koubek Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra . . . . . . . . . . . . 203--216 M. Kaminski A classification of omega-regular languages . . . . . . . . . . . . . . . 217--229 E. Allender and M. M. Klawe Improved lower bounds for the cycle detection problem . . . . . . . . . . . 231--237 R. Fagin and M. M. Klawe and N. J. Pippenger and L. Stockmeyer Bounded-depth, polynomial-size circuits for symmetric functions . . . . . . . . 239--250 L. Farinas Del Cerro and E. Orlowska DAL-a logic for data analysis . . . . . 251--264 M. R. Jerrum The complexity of finding minimum-length generator sequences . . . . . . . . . . 265--289 H. Matsuno and K. Inoue and H. Taniguchi and I. Takanami Alternating simple multihead finite automata . . . . . . . . . . . . . . . . 291--308 W. Keller-Gehrig Fast algorithms for the characteristic polynomial . . . . . . . . . . . . . . . 309--317 K. Diks Embeddings of binary trees in lines . . 319--331 H. Alt Multiplication is the easiest nontrivial arithmetic function . . . . . . . . . . 333--339 W. Rytter and M. Chrobak A characterization of reversal-bounded multipushdown machine languages . . . . 341--344 G. Farr and C. McDiarmid The complexity of counting homeomorphs 345--348
K. Ko On some natural complete operators . . . 1--30 G. Rozenberg On coordinated selective substitutions: towards a unified theory of grammars and machines . . . . . . . . . . . . . . . . 31--50 D. E. Muller and P. E. Schupp The theory of ends, pushdown automata, and second-order logic . . . . . . . . . 51--75 J. A. Bergstra and J. W. Klop Algebra of communicating processes with abstraction . . . . . . . . . . . . . . 77--121
J. H. Gallier and R. V. Book Reductions in tree replacement systems 123--150 L. Bouge A contribution to the theory of program testing . . . . . . . . . . . . . . . . 151--181 K. Culik, II and I. Fris Topological transformations as a tool in the design of systolic networks . . . . 183--216 J. Gonczarowski and M. K. Warmuth Applications of scheduling theory to formal language theory . . . . . . . . . 217--243
R. de Simone Higher-level synchronising devices in MEIJE-SCCS . . . . . . . . . . . . . . . 245--267 A. Tarlecki On the existence of free models in abstract algebraic institutions . . . . 269--304 P. Darondeau About fair asynchrony . . . . . . . . . 305--336 A. Ehrenfeucht and H. C. M. Kleijn and G. Rozenberg Adding global forbidding context to context-free grammars . . . . . . . . . 357--360
M. P. Fle and G. Roucairol Maximal serializability of iterated transactions . . . . . . . . . . . . . . 1--16 K. Weihrauch Type 2 recursion theory . . . . . . . . 17--33 C. Kreitz and K. Weihrauch Theory of representations . . . . . . . 35--53 I. Wegener On the complexity of slice functions . . 55--68 M. Snir Lower bounds on probabilistic linear decision trees . . . . . . . . . . . . . 69--82 P. V. Ramanan and C. L. Liu Permutation representation of $k$-ary trees . . . . . . . . . . . . . . . . . 83--98 C. Beeri and M. Y. Vardi Formal systems for join dependencies . . 99--116 M. Leconte A characterization of power-free morphisms . . . . . . . . . . . . . . . 117--122 D. L. Van Code-compatible sets and a generalisation of the Sardinas-Patterson theorem . . . . . . . . . . . . . . . . 123--132 E. Leiss Succinct representation of regular languages by Boolean automata. II . . . 133--136 A. Finkel A generalisation of the theorems of Higman and of Simon to infinite words 137--142
D. Schmidt The recursion-theoretic structure of complexity classes . . . . . . . . . . . 143--156 O. Watanabe On one-one polynomial time equivalence relations . . . . . . . . . . . . . . . 157--165 M. Imori and H. Yamada Periodic character sequences where identifying two characters strictly reduces the period . . . . . . . . . . . 167--192 H. D. Burkhard An investigation of controls for concurrent systems based on abstract control languages . . . . . . . . . . . 193--122 M. Jantzen Extending regular expressions with iterated shuffle . . . . . . . . . . . . 223--247 T. Asano An approach to the subgraph homeomorphism problem . . . . . . . . . 249--267 B. Mishra and E. Clarke Hierarchical verification of asynchronous circuits using temporal logic . . . . . . . . . . . . . . . . . 269--291 T. F. Gonzalez Clustering to minimize the maximum intercluster distance . . . . . . . . . 293--306 D. Harel and D. Peleg Process logic with regular formulas . . 307--322 D. J. Rosenkrantz and H. B. Hunt, III Testing for grammatical coverings . . . 323--341 N. Linial and M. Tarsi Deciding hypergraph $2$-colourability by H-resolution . . . . . . . . . . . . . . 343--347
Anonymous Third Conference on Foundations of Software Technology and Theoretical Computer Science . . . . . . . . . . . . ?? C. Frougny Context-free grammars with cancellation properties . . . . . . . . . . . . . . . 3--13 J.-L. Lassez and M. J. Maher Optimal fixedpoints of logic programs 15--25 C. Stirling A proof-theoretic characterization of observational equivalence . . . . . . . 27--45 R. J. R. Back and H. Mannila On the suitability of trace semantics for modular proofs of communicating processes . . . . . . . . . . . . . . . 47--68 R. Kannan Solving systems of linear equations over polynomials . . . . . . . . . . . . . . 69--88
O. H. Ibarra and M. A. Palis and J. H. Chang On efficient recognition of transductions and relations . . . . . . 89--106 L. Priese On a fast decomposition method in some models of concurrent computations . . . 107--121 D. Kapur and P. Narendran and M. S. Krishnamoorthy and McNaughton and R. The Church--Rosser property and special Thue systems . . . . . . . . . . . . . . 123--133 Corrado Böhm and Alessandro Berarducci Automatic synthesis of typed $\Lambda$-programs on term algebras . . 135--153 M. Parigot and E. Pelz A logical approach of Petri net languages . . . . . . . . . . . . . . . 155--169 J.-C. Spehner Entire systems of equations on a finite alphabet and Ehrenfeucht's conjecture 171--188 M. Rodriguez Artalejo Some questions about expressiveness and relative completeness in Hoare's logic 189--206 S. R. Mahaney and P. Young Reductions among polynomial isomorphism types . . . . . . . . . . . . . . . . . 207--224 D. Joseph and P. Young Some remarks on witness functions for nonpolynomial and noncomplete sets in NP 225--237 R. Hull Non-finite specifiability of projections of functional dependency families . . . 239--265 J. Vogel and K. Wagner Two-way automata with more than one storage medium . . . . . . . . . . . . . 267--280 R. Siromoney and V. R. Dare On infinite words obtained by selective substitution grammars . . . . . . . . . 281--295 A. Haken The intractability of resolution . . . . 297--308 S. Ginsburg and E. H. Spanier On completing tables to satisfy functional dependencies . . . . . . . . 309--317 R. V. Book and F. Otto On the security of name-stamp protocols 319--325 E. L. Leiss On solving star equations . . . . . . . 327--332 A. Arnold A syntactic congruence for rational omega-languages . . . . . . . . . . . . 333--335 M. W. Bunder An extension of Klop's counterexample to the Church--Rosser property to lambda-calculus with other ordered pair combinators . . . . . . . . . . . . . . 337--342
J. Karhumaki On three-element codes . . . . . . . . . 3--11 A. Restivo and C. Reutenauer Rational languages and the Burnside problem . . . . . . . . . . . . . . . . 13--30 A. Blumer and J. Blumer and D. Haussler and A. Ehrenfeucht and Chen and M. T. and J. Seiferas The smallest automation recognizing the subwords of a text . . . . . . . . . . . 31--55 U. Schoning Robust algorithms: a different approach to oracles . . . . . . . . . . . . . . . 57--66 R. Paige and R. E. Tarjan and R. Bonic A linear time solution to the single function coarsest partition problem . . 67--84
G. Bauer n-level rewriting systems . . . . . . . 85--99 R. V. Book and F. Otto On the verifiability of two-party algebraic protocols . . . . . . . . . . 101--130 W. Bucher and A. Ehrenfeucht and D. Haussler On total regulators generated by derivation relations . . . . . . . . . . 131--148 I. J. J. Aalbersberg and G. Rozenberg CTS systems and Petri nets . . . . . . . 149--162 K. Ayers Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages . . . . . . . . . . . . . . . 163--174 K. Kobayashi On the structure of one-tape nondeterministic Turing machine time hierarchy . . . . . . . . . . . . . . . 175--193 Ming-Deh A. Huang and K. J. Lieberherr Implications of forbidden structures for extremal algorithmic problems . . . . . 195--210 G. Mascari and M. Venturini Zilli While-programs with nondeterministic assignments and the logic ALNA . . . . . 211--235 J. L. Balcazar and R. V. Book and U. Schoning On bounded query machines . . . . . . . 237--243 T. Kanaoka and S. Tomita Homogeneous decomposition of stochastic systems . . . . . . . . . . . . . . . . 245--255 S. K. Abdali and B. D. Saunders Transitive closure and related semiring properties via eliminants . . . . . . . 257--274 F. Fogelman-Soulie Parallel and sequential computation on Boolean networks . . . . . . . . . . . . 275--300 A. Ginzburg and M. Yoeli Reducibility of synchronization structures . . . . . . . . . . . . . . . 301--314 F. J. Urbanek On Greibach normal form construction . . 315--317 M. Kaminski A lower bound for polynomial multiplication . . . . . . . . . . . . . 319--322 M. S. Krishnamoorthy and P. Narendran On recursive path ordering . . . . . . . 323--328 G. Gonthier Algebraic calculi of processes and net expressions . . . . . . . . . . . . . . 329--337
G. P\uaun A variant of random context grammars: semi-conditional grammars . . . . . . . 1--17 E. Goles Dynamics of positive automata networks 19--32 V. E. Cazanescu On context-free trees . . . . . . . . . 33--50 P. Gohon An algorithm to decide whether a rational subset of $N^k$ is recognizable 51--59 E. Barbin-Le Rest and M. Le Rest On the combinatorial of two-word codes 61--80 C. S. Iliopoulos Computing in general Abelian groups is hard . . . . . . . . . . . . . . . . . . 81--93 S. Hayashi Adjunction of semifunctors: categorical structures in nonextensional Lambda calculus . . . . . . . . . . . . . . . . 95--104 Y. Maon On the equivalence problem of compositions of morphisms and inverse morphisms on context-free languages . . 105--107 J.-Y. Thibon Integrity of algebras of formal series on a partially commutative alphabet . . 109--112 M. W. Bunder Possible forms of evaluation or reduction in Martin-Löf type theory . . . 113--120 M. H. Albert and J. Lawrence A proof of Ehrenfeucht's conjecture . . 121--123
B. Helfrich Algorithms to construct Minkowski reduced and Hermite reduced lattice bases . . . . . . . . . . . . . . . . . 125--139 B. Monien and I. H. Sudborough Bandwidth constrained NP-complete problems . . . . . . . . . . . . . . . . 141--167 E. Dahlhaus and H. Gaifman Concerning two-adjacent context-free languages . . . . . . . . . . . . . . . 169--184 W. Reisig Petri nets with individual tokens . . . 185--213 J. Karhumaki A property of three-element codes . . . 215--222 E. Tomita and K. Seino A weaker sufficient condition for the equivalence of a pair of DPDAs to be decidable . . . . . . . . . . . . . . . 223--230 O. H. Ibarra and M. A. Palis and S. M. Kim Fast parallel language recognition by cellular automata . . . . . . . . . . . 231--246 E. Pelz On the complexity of theories of permutations . . . . . . . . . . . . . . 247--269 J. Grant and J. Minker Inferences for numerical dependencies 271--287 S. Hirokawa Complexity of the combinator reduction machine . . . . . . . . . . . . . . . . 289--303 G. Slutzki Alternating tree automata . . . . . . . 305--318 H.-J. Stoss The complexity of evaluating interpolation polynomials . . . . . . . 319--323 F. Meyer Auf Der Heide Simulating probabilistic by deterministic algebraic computation trees . . . . . . . . . . . . . . . . . 325--330 K. Inoue and I. Takanami and R. Vollmar Alternating on-line Turing machines with only universal states and small space bounds . . . . . . . . . . . . . . . . . 331--339
B. Courcelle Equivalences and transformations of regular systems-applications to recursive program schemes and grammars 1--122
M. Wirsing Structured algebraic specifications: a kernel language . . . . . . . . . . . . 123--249
J. Engelfriet and H. Vogler Pushdown machines for the macro tree transducer . . . . . . . . . . . . . . . 251--368
J. W. Grzymala-Busse and Z. Bavel Characterization of state-independent automata . . . . . . . . . . . . . . . . 1--10 A. Scheuing Decomposition of linear automata over residue rings into shift-registers . . . 11--30 C. Ronse A topological characterization of thinning . . . . . . . . . . . . . . . . 31--41 L. M. Goldschlager and I. Parberry On the construction of parallel computers from various bases of Boolean functions . . . . . . . . . . . . . . . 43--58 R. R. Redziejowski Infinite-word languages and continuous mappings . . . . . . . . . . . . . . . . 59--79 E. Orlowska Semantic analysis of inductive reasoning 81--89 G. Hansel The demonstration of a simple proof of Skolem-Mahler-Lech theorem . . . . . . . 91--98 P. Clote On the finite containment problem for Petri nets . . . . . . . . . . . . . . . 99--105 P. A. Lindsay Alternation and omega-type Turing acceptors . . . . . . . . . . . . . . . 107--115 M. H. Albert and J. Lawrence Test sets for finite substitutions . . . 117--122
R. Berghammer and H. Zierer Relational algebraic semantics of deterministic and nondeterministic programs . . . . . . . . . . . . . . . . 123--147 J. Heering Partial evaluation and omega-completeness of algebraic specifications . . . . . . . . . . . . . 149--167 M. R. Jerrum and L. G. Valiant and V. V. Vazirani Random generation of combinatorial structures from a uniform distribution 169--188 F. Fages and G. Huet Complete sets of unifiers and matchers in equational theories . . . . . . . . . 189--200 I. Wegener More on the complexity of slice functions . . . . . . . . . . . . . . . 201--211 R. Janicki and P. E. Lauer and M. Koutny and R. Devillers Concurrent and maximally concurrent evolution of nonsequential systems . . . 213--238 G. M. Landau and U. Vishkin Efficient string matching with k mismatches . . . . . . . . . . . . . . . 239--249 A. Pasztor and R. Statman Scott induction and closure under omega-sups . . . . . . . . . . . . . . . 251--263 A. de Luca and A. Restivo Star-free sets of integers . . . . . . . 265--275 I. Suzuki and Y. Motohashi and K. Taniguchi and T. Kasami and T. Okamoto Specification and verification of decentralized daisy chain arbiters with omega-extended regular expressions . . . 277--291 J. Adamek and J. Reiterman and E. Nelson Continuous semilattices . . . . . . . . 293--313 A. Saoudi Varieties of automata deriving from infinite trees . . . . . . . . . . . . . 315--335 K. Edwards The complexity of colouring problems on dense graphs . . . . . . . . . . . . . . 337--343 D. B. Johnson A simple proof of a time-space trade-off for sorting with linear comparisons . . 345--350
P. Ritzmann A fast numerical algorithm for the composition of power series with complex coefficients . . . . . . . . . . . . . . 1--16 F. Blanchard and G. Hansel Coded systems . . . . . . . . . . . . . 17--49 D. Leivant Typing and computational properties of lambda expressions . . . . . . . . . . . 51--68 L. E. Rosier and H.-C. Yen Boundedness, empty channel detection, and synchronization for communicating finite automata . . . . . . . . . . . . 69--105 F. Blanchard and S. Martinez Dense orbit points of certain languages of infinite words . . . . . . . . . . . 107--110 J. H. Chang and O. H. Ibarra and M. A. Palis and B. Ravikumar On pebble automata . . . . . . . . . . . 111--121
E. Paul On solving the equality problem in theories defined by Horn clauses . . . . 127--153 E. L. Leiss Generalized language equations with multiple solutions . . . . . . . . . . . 155--174 Y. Kobayashi Repetition-free words . . . . . . . . . 175--197 V. Diekert Complete semi-Thue systems for Abelian groups . . . . . . . . . . . . . . . . . 199--208 T. Etzion An algorithm for generating shift-register cycles . . . . . . . . . 209--224 S. Okawa and S. Hirose and M. Yoneda On the impossibility of the homomorphic characterization of context-sensitive languages . . . . . . . . . . . . . . . 225--228 F. J. Urbanek On Greibach normal form construction . . 229--236 P. Narendran On the equivalence problem for regular Thue systems . . . . . . . . . . . . . . 237--245
P. E. Dunne The complexity of central slice functions . . . . . . . . . . . . . . . 247--257 M. Takahashi The greatest fixed-points and rational omega-tree languages . . . . . . . . . . 259--274 H.-J. Kreowski and A. Wilharm Net processes correspond to derivation processes in graph grammars . . . . . . 275--305 W. F. Dowling and J. H. Gallier Continuation semantics for flowgraph equations . . . . . . . . . . . . . . . 307--331 E. T. Poulsen The Ehrenfeucht Conjecture: an algebra-framework for its proof . . . . 333--339
M. Broy A theory for nondeterminism, parallelism, communication, and concurrency . . . . . . . . . . . . . . 1--61 M. Crochemore Transducers and repetitions . . . . . . 63--86 J. Gonczarowski Manipulating derivation forests by scheduling techniques . . . . . . . . . 87--119
M. Dezani-Ciancaglini and I. Margaria A characterization of F-complete type assignments . . . . . . . . . . . . . . 121--157 J.-Y. Girard The system F of variable types, fifteen years later . . . . . . . . . . . . . . 159--192 J.-J. Ch. Meyer Merging regular processes by means of fixed-point theory . . . . . . . . . . . 193--260
P. Huber and A. M. Jensen and L. O. Jepsen and K. Jensen Reachability trees for high-level Petri nets . . . . . . . . . . . . . . . . . . 261--292 H. Ait-Kaci An algebraic semantics approach to the effective resolution of type equations 293--351
G. Bernot and M. Bidoit and C. Choppy Abstract data types with exception handling: an initial approach based on a distinction between exceptions and errors . . . . . . . . . . . . . . . . . 13--45 Y. Q. Guo and G. W. Xu and G. Thierrin Disjunctive decomposition of languages 47--51 K. Hashiguchi Notes on finitely generated semigroups and pumping conditions for regular languages . . . . . . . . . . . . . . . 53--66 N. Lerat and W. Lipski, Jr. Nonapplicable nulls . . . . . . . . . . 67--82 T. Head and B. Lando Periodic D0L languages . . . . . . . . . 83--89 H. Yamasaki and M. Takahashi and K. Kobayashi Characterization of omega-regular languages by monadic second-order formulas . . . . . . . . . . . . . . . . 91--99 M. Latteux and E. Timmerman Two characterizations of rational adherences . . . . . . . . . . . . . . . 101--106
R. R. Howell and L. E. Rosier and Dung T. Huynh and Hsu-Chun Yen Some complexity bounds for problems concerning finite and $2$- dimensional vector addition systems with states . . 107--140 J. Jaffar and P. J. Stuckey Semantics of infinite tree logic programming . . . . . . . . . . . . . . 141--158 C. Duboc On some equations in free partially commutative monoids . . . . . . . . . . 159--174 A. Brazma and E. Kinber Generalized regular expressions --- a language for synthesis of programs with branching in loops . . . . . . . . . . . 175--195 G. Longo and S. Martini Computability in higher types, P omega and the completeness of type assignment 197--217 Phan Dinh Dieu and Le Cong Thanh and Le Tuan Hoa Average polynomial time complexity of some NP-complete problems . . . . . . . 219--237 P. Hajek A simple dynamic logic . . . . . . . . . 239--259 Chua-Huang Huang and C. Lengauer The automated proof of a trace transformation for a bitonic sort . . . 261--284 A. Dicky An algebraic and algorithmic method for analysing transition systems . . . . . . 285--303 T. Hardin and A. Laville Proof of termination of the rewriting system SUBST on CCL . . . . . . . . . . 305--312 V. Diekert On some variants of the Ehrenfeucht Conjecture . . . . . . . . . . . . . . . 313--318 V. Diekert Commutative monoids have complete presentations by free (non-commutative) monoids . . . . . . . . . . . . . . . . 319--327 B. Griesser Lower bounds for the approximative complexity . . . . . . . . . . . . . . . 329--338
Z. Esik and P. Domosi Complete classes of automata for the $\alpha_0$-product . . . . . . . . . . . 1--14 K. Culik, II and Sheng Yu Real-time, pseudo real-time, and linear-time ITA . . . . . . . . . . . . 15--26 P. Narendran and F. Otto The problems of cyclic equality and conjugacy for finite complete rewriting systems . . . . . . . . . . . . . . . . 27--38 J. H. Johnson Rational equivalence relations . . . . . 39--60 A. Pelc Lie patterns in search procedures . . . 61--69 K. Culik, II and J. Karhumaki The equivalence of finite valued transducers (on HDT0L languages) is decidable . . . . . . . . . . . . . . . 71--84 L. G. Valiant and V. V. Vazirani NP is as easy as detecting unique solutions . . . . . . . . . . . . . . . 85--93 J.-P. Pecuchet On the complementation of Buchi Automata 95--98 J. Heintz On polynomials with symmetric Galois group which are easy to compute . . . . 99--105 P. Wyrostek On the size of unambiguous context-free grammars . . . . . . . . . . . . . . . . 107--110
P. W. Dymond On nondeterminism in parallel computation . . . . . . . . . . . . . . 111--120 P. Orponen A classification of complexity core lattices . . . . . . . . . . . . . . . . 121--130 K. W. Wagner Some observations on the connection between counting and recursion . . . . . 131--147 M. Chrobak Finite automata and unary languages . . 149--158 V. R. Dare and R. Siromoney Subword topology . . . . . . . . . . . . 159--168 S. Homer On simple and creative sets in NP . . . 169--180 J.-C. Spehner The rapid calculation of shuffles of two words . . . . . . . . . . . . . . . . . 191--203 L. M. Kirousis and C. H. Papadimitriou Searching and pebbling . . . . . . . . . 205--218 R. Parchmann and J. Duske Self-embedding indexed grammars . . . . 219--223 F. Otto The undecidability of self-embedding for finite semi-Thue and Thue systems . . . 225--232
M. Karchmer Two time-space tradeoffs for element distinctness . . . . . . . . . . . . . . 237--246 Y. Maon and A. Yehudai Balance of many-valued transductions and equivalence problems . . . . . . . . . . 247--262 Ker-I Ko and T. J. Long and D.-Z. Du On one-way functions and polynomial-time isomorphisms . . . . . . . . . . . . . . 263--276 Y. Maon and B. Schieber and U. Vishkin Parallel ear decomposition search (EDS) and st-numbering in graphs . . . . . . . 277--298 Ker-I Ko On the continued fraction representation of computable real numbers . . . . . . . 299--313 W. Rytter On the complexity of parallel parsing of general context-free languages . . . . . 315--321 J. W. Hong and Q. Zuo Lower bounds on communication overlap of networks . . . . . . . . . . . . . . . . 323--328 Z. Szalas Concerning the semantic consequence relation in first-order temporal logic 329--334 J.-L. Deleage and L. Pierre The rational index of the Dyck language $D_1'*$ . . . . . . . . . . . . . . . . 335--343
Z. Esik and F. Gecseg On $\alpha_0$-products and $\alpha_2$-products . . . . . . . . . . 1--8 K.-I. Ko On the notion of infinite pseudorandom sequences . . . . . . . . . . . . . . . 9--33 J.-C. Spehner The occurrence of the factors of a given word in a text . . . . . . . . . . . . . 35--52 S. Bublitz and U. Schurfeld and I. Wegener and B. Voigt Properties of complexity measures for PRAMs and WRAMs . . . . . . . . . . . . 53--73 C. P. Kruskal and M. Snir A unified theory of interconnection network structure . . . . . . . . . . . 75--94 R. Statman Every countable poset is embeddable in the poset of unsolvable terms . . . . . 95--100 T. Head and B. Lando Regularity of sets of initial strings of periodic D0L-systems . . . . . . . . . . 101--108 J. Hromkovic Communication complexity hierarchy . . . 109--115 G. Berry and R. Sethi From regular expressions to deterministic automata . . . . . . . . . 117--126 V. Weispfenning The complexity of the word problem for Abelian $l$-groups . . . . . . . . . . . 127--132
M. Tchuente Sequential simulation of parallel iterations and applications . . . . . . 135--144 W. Marek and H. Rasiowa Approximating sets with equivalence relations . . . . . . . . . . . . . . . 145--152 M. Chrobak Hierarchies of one-way multihead automata languages . . . . . . . . . . . 153--181 C. Duboc Mixed product and asynchronous automata 183--199 A. Ehrenfeucht and H. J. Hoogeboom and G. Rozenberg On the active and full use of memory in right-boundary grammars and push-down automata . . . . . . . . . . . . . . . . 201--228 M. Fitting Partial models and logic programming . . 229--255 W. Danko First-order approximation of algorithmic theories . . . . . . . . . . . . . . . . 257--272 G. F. Italiano Amortized efficiency of a path retrieval data structure . . . . . . . . . . . . . 273--281 A. Salomaa and S. Yu On a public-key cryptosystem based on iterated morphisms and substitutions . . 283--296 S. Ginsburg and C. Tang Projection of object histories . . . . . 297--328 A. Gibbons and W. Rytter On the decidability of some problems about rational subsets of free partially commutative monoids . . . . . . . . . . 329--337
M. Takahashi Brzozowski hierarchy of omega-languages 1--12 C. C. Squier Units of special Church--Rosser monoids 13--22 R. Parchmann and J. Duske Grammars, derivation modes and properties of indexed and type-0 languages . . . . . . . . . . . . . . . 23--42 M. Oyamaguchi The Church--Rosser property for ground term-rewriting systems is decidable . . 43--79 L. J. Guibas and J. Stolfi and K. L. Clarkson Solving related two- and three-dimensional linear programming problems in logarithmic time . . . . . . 81--84
Anonymous Twelfth International Colloquium on Automata, Languages and Programming . . ?? J. W. de Bakker and J.-J. C. Meyer and E.-R. Olderog Infinite streams and finite observations in the semantics of uniform concurrency 87--112 M. G. Main and W. Bucher and D. Haussler Applications of an infinite square-free co-CFL . . . . . . . . . . . . . . . . . 113--119 M. Hennessy An algebraic theory of fair asynchronous communicating processes . . . . . . . . 121--143 L. Bouge Repeated snapshots in distributed systems with synchronous communications and their implementation in CSP . . . . 145--169 Z. Galil and G. M. Landau and M. M. Yung Distributed algorithms in synchronous broadcasting networks . . . . . . . . . 171--184 K. G. Larsen A context dependent equivalence between processes . . . . . . . . . . . . . . . 185--215 A. Prasad Sistla and M. Y. Vardi and P. Wolper The complementation problem for Buchi automata with applications to temporal logic . . . . . . . . . . . . . . . . . 217--237 R. Cole Partitioning point sets in arbitrary dimension . . . . . . . . . . . . . . . 239--265 T. G. Kurtz and U. Manber A probabilistic distributed algorithm for set intersection and its analysis 267--282 P. Flajolet Analytic models and ambiguity of context-free languages . . . . . . . . . 283--309 C. Stirling Modal logics for communicating systems 311--347
J.-Y. Girard Linear logic . . . . . . . . . . . . . . 1--102
J. W. Gray Categorical aspects of data type constructors . . . . . . . . . . . . . . 103--135 J. A. Bergstra and J. V. Tucker Algebraic specifications of computable and semicomputable data types . . . . . 137--181 J. Mazoyer A six-state minimal time solution to the firing squad synchronization problem . . 183--238
I. Phillips Refusal testing . . . . . . . . . . . . 241--284 I. Sain Total correctness in nonstandard logics of programs . . . . . . . . . . . . . . 285--321 E. G. Wagner and H. Ehrig Canonical constraints for parameterized data types . . . . . . . . . . . . . . . 323--349
A. S. Troelstra On the syntax of Martin-Löf's type theories . . . . . . . . . . . . . . . . 1--26 P. Le Chenadec Analysis of Dehn's algorithm by critical pairs . . . . . . . . . . . . . . . . . 27--52 K. W. Wagner More complicated questions about maxima and minima, and some closures of NP . . 53--80 A. Habel and H. J. Kreowski Characteristics of graph languages generated by edge replacement . . . . . 81--115 J. Beauquier and F. Gire A note on the characterisation theorem for algebraic generators . . . . . . . . 117--127 J. C. M. Baeten and J. A. Bergstra and J. W. Klop On the consistency of Koomen's fair abstraction rule . . . . . . . . . . . . 129--176 K. Ambos-Spies and H. Fleischhack and H. Huwig Diagonalizations over polynomial time computable sets . . . . . . . . . . . . 177--204 F. Orejas A characterization of passing compatibility for parameterized specifications . . . . . . . . . . . . . 205--214 A. Carpi On unambiguous reductions of monoids of unambiguous relations . . . . . . . . . 215--220 J. Vyskoc An $O(n^{lgk}.2^n2)$ time and $O(k.2^nk)$ space algorithm for certain NP-complete problems . . . . . . . . . . 221--227 E. G. Belaga Constructive universal algebra: an introduction . . . . . . . . . . . . . . 229--238 I. Parberry On the time required to sum n semigroup elements on a parallel machine with simultaneous writes . . . . . . . . . . 239--247
T. Head and B. Lando Bounded DL languages . . . . . . . . . . 255--264 S. Homer and T. J. Long Honest polynomial degrees and P=?NP . . 265--280 B. Bérard Literal shuffle (formal languages) . . . 281--299 T. Yokomori On purely morphic characterizations of context-free languages . . . . . . . . . 301--308 S. Yamasaki and M. Yoshida and S. Doshita A fixpoint semantics of Horn sentences based on substitution sets . . . . . . . 309--324 J. Hromkovic Reversal-bounded nondeterministic multicounter machines and complementation . . . . . . . . . . . . 325--330 T. Beth On the computational complexity of the general discrete Fourier transform . . . 331--339 Z. Galil and R. Giancarlo Parallel string matching with k mismatches . . . . . . . . . . . . . . . 341--348
M. Zaionc Word operation definable in the typed lambda-calculus . . . . . . . . . . . . 1--14 K. I. Ko On helping by robust oracle machines . . 15--36 R. Kennaway On 'On graph rewritings' . . . . . . . . 37--58 J. Sakarovitch On regular trace languages . . . . . . . 59--75 J. von zur Gathen Factoring polynomials and primitive elements for special primes . . . . . . 77--89 B. Seite A Yacc extension for LRR grammar parsing 91--143 D. Mundici Satisfiability in many-valued sentential logic is NP-complete . . . . . . . . . . 145--153 P. Spirakis The parallel complexity of deadlock detection . . . . . . . . . . . . . . . 155--163 T. Moriya Topological characterizations of infinite tree languages . . . . . . . . 165--171
C. Kim and I. H. Sudborough The membership and equivalence problems for picture languages . . . . . . . . . 177--191 J. M. Marberg and E. Gafni Distributed sorting algorithms for multi-channel broadcast networks . . . . 193--203 M. Felleisen and D. P. Friedman and E. Kohlbecker and B. Duba A syntactic theory of sequential control 205--237 R. G. Nigmatullin Models of lower-bounds proofs . . . . . 239--249 J. L. Balcazar and J. Diaz and J. Gabarro On characterizations of the class PSPACE\slash poly . . . . . . . . . . . 251--267 E. Gelenbe and D. Finkel Stationary deterministic flows. II. The single-server queue . . . . . . . . . . 269--280 R. W. Topor Domain-independent formulas and databases . . . . . . . . . . . . . . . 281--306 G. Stefanescu On flowchart theories. II. The nondeterministic case . . . . . . . . . 307--340 F. J. Brandenburg Comments on 'Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages' . . . . . . . . . . . . . . . 341--342
Anonymous Eleventh Colloquium on Trees in Algebra and Programming . . . . . . . . . . . . ?? E. G. Wagner A categorical treatment of pre- and post-conditions . . . . . . . . . . . . 3--24 G. File Classical and incremental attribute evaluation by means of recursive procedures . . . . . . . . . . . . . . . 25--65 D. Frutos Escrig Probabilistic Ianov's schemes . . . . . 67--97 G. Louchard Random walks, Gaussian processes and list structures . . . . . . . . . . . . 99--124 A. Pelin and J. H. Gallier Building exact computation sequences . . 125--150 A. Pettorossi Derivation of efficient programs for computing sequences of actions . . . . . 151--167
H. Attiya and Y. Mansour Language complexity on the synchronous anonymous ring . . . . . . . . . . . . . 169--185 I. Litovsky and E. Timmerman On generators of rational omega-power languages . . . . . . . . . . . . . . . 187--200 C. P. Schnorr A hierarchy of polynomial time lattice basis reduction algorithms . . . . . . . 201--224 S. Abramsky Observation equivalence as a testing equivalence . . . . . . . . . . . . . . 225--241 Z. Esik and F. Gecseg On a representation of tree automata . . 243--255 H. Muller and A. Brandstadt The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs . . . . . . . . . . . . . . . . . 257--265 M. Beynon and J. Buckle On the planar monotone computation of Boolean functions . . . . . . . . . . . 267--279 D. Peleg and E. Upfal The generalized packet routing problem 281--293 W. Rytter and R. Giancarlo Optimal parallel parsing of bracket languages . . . . . . . . . . . . . . . 295--306 M. Garzon Cyclic automata . . . . . . . . . . . . 307--317 T. Nishida and Y. Kobuchi Repeatable words for substitution . . . 319--333 L. Hallnas An intensional characterization of the largest bisimulation . . . . . . . . . . 335--343 N. Santoro and J. B. Sidney and S. J. Sidney and J. Urrutia Geometric containment and vector dominance . . . . . . . . . . . . . . . 345--352
Jieh Hsiang and M. Srivas Automatic inductive theorem proving using PROLOG . . . . . . . . . . . . . . 3--28 F. V. Jensen and K. D. Larsen Recursively defined domains and their induction principles . . . . . . . . . . 29--51 A. Marchetti-Spaccamela New protocols for the election of a leader in a ring . . . . . . . . . . . . 53--64 V. Pan Complexity of parallel matrix computations . . . . . . . . . . . . . . 65--85 C. Bajaj Geometric optimization and the polynomial hierarchy . . . . . . . . . . 87--102 V. S. Lakshmanan and C. E. Veni Madhavan An algebraic theory of functional and multivalued dependencies in relational databases . . . . . . . . . . . . . . . 103--128 S. M. Venkatesan Approximation algorithms for weighted matching . . . . . . . . . . . . . . . . 129--137
L. Priese and R. Rehrmann and U. Willecke-Klemme An introduction to the regular theory of fairness . . . . . . . . . . . . . . . . 139--163 G. Rindone Construction of a family of codes associated with certain finite groups 165--179 A. Brandstadt and D. Kratsch On domination problems for permutation and other graphs . . . . . . . . . . . . 181--198 A. Szalas A complete axiomatic characterization of first-order temporal logic of linear time . . . . . . . . . . . . . . . . . . 199--214 J. R. B. Cockett Discrete decision theory: manipulations 215--236 P. Bertolazzi and A. Sassano An O(mn) algorithm for regular set-covering problems . . . . . . . . . 237--247 O. Watanabe A comparison of polynomial time completeness notions . . . . . . . . . . 249--265 D. E. Muller and P. E. Schupp Alternating automata on infinite trees 267--276 H. Fauconnier Asynchronous semantics and infinite behaviour in CSP . . . . . . . . . . . . 277--298 S. Ginsburg and Chang-jie Tang Canonical forms for interval functions 299--313 K. Sado and Y. Igarashi A function for evaluating the computing time of a bubbling system . . . . . . . 315--324 S. Iwata and T. Kasai Simultaneous (poly-time, log-space) lower bounds . . . . . . . . . . . . . . 325--329 M. Liskiewicz and K. Lorys and M. Piotrow On reversal bounded alternating Turing machines . . . . . . . . . . . . . . . . 331--339 K.-I. Ko On the continued fraction representation of computable real numbers . . . . . . . 341--343
D. Peleg Concurrent program schemes and their logics . . . . . . . . . . . . . . . . . 1--45 H. Seidl Parameter-reduction of higher level grammars . . . . . . . . . . . . . . . . 47--85 E. Best and R. Devillers Sequential and concurrent behaviour in Petri net theory . . . . . . . . . . . . 87--136
B. Courcelle An axiomatic definition of context-free rewriting and its application to NLC graph grammars . . . . . . . . . . . . . 141--181 F.-J. Brandenburg Representations of language families by homomorphic equality operations and generalized equality sets . . . . . . . 183--263 M. Bartha An equational axiomatization of systolic systems . . . . . . . . . . . . . . . . 265--289 J.-P. Lehmann A universal machine without change of state . . . . . . . . . . . . . . . . . 291--348
D. Armbruster A polynomial determination of the most-recent property in Pascal-like programs . . . . . . . . . . . . . . . . 3--15 C. Hankin and G. Burn and S. Peyton Jones A safe approach to parallel combinator reduction . . . . . . . . . . . . . . . 17--36 S. Kaplan Rewriting with a nondeterministic choice operator . . . . . . . . . . . . . . . . 37--57 F. Nielson and H. R. Nielson Two-level semantics and code generation 59--133 E. W. Stark Proving entailment between conceptual state specifications . . . . . . . . . . 135--154
E. Fachini and M. Napoli C-tree systolic automata . . . . . . . . 155--186 W. Marek A natural semantics for modal logic over databases . . . . . . . . . . . . . . . 187--209 C. S. Iliopoulos On the computational complexity of the Abelian permutation group structure, membership and intersection problems . . 211--222 S. Sekimoto and S. Hirokawa One-step recurrent terms in $\lambda$-$\beta$-calculus . . . . . . . 223--231 A. Carpi Multidimensional unrepetitive configurations . . . . . . . . . . . . . 233--241 J. Mohrherr A remark on the length problem . . . . . 243--248
C. Tretkoff Complexity, combinatorial group theory and the language of palutators . . . . . 253--275 J. Staples Delaying unification algorithms for lambda calculi . . . . . . . . . . . . . 277--288 E. Gradel Subclasses of Presburger arithmetic and the polynomial-time hierarchy . . . . . 289--301 A. Martino A quantitative interpretation of Girard's system $F$ . . . . . . . . . . 303--320 R. Boonyavatana and G. Slutzki The interchange or pump (DI)lemmas for context-free languages . . . . . . . . . 321--338 V. Bruyere An answer to a question about finite maximal prefix sets of words . . . . . . 339--344 F. Baader and W. Buttner Unification in commutative idempotent monoids . . . . . . . . . . . . . . . . 345--353
M. Broy Equational specification of partial higher-order algebras . . . . . . . . . 3--45 O. H. Ibarra and M. A. Palis Two-dimensional iterative arrays: characterizations and applications . . . 47--86 F. M. Ablyv The complexity properties of probabilistic automata with isolated cut point . . . . . . . . . . . . . . . . . 87--95 J. Hromkovic The advantages of a new approach to defining the communication complexity for VLSI . . . . . . . . . . . . . . . . 97--111 S. P. Jukna Entropy of contact circuits and lower bounds on their complexity . . . . . . . 113--129 Jorma Tarhio and Esko Ukkonen A greedy approximation algorithm for constructing shortest common superstrings . . . . . . . . . . . . . . 131--145 W. Kuich Matrix systems and principal cones of algebraic power series . . . . . . . . . 147--152 Wladyslaw Skarbek Generating ordered trees . . . . . . . . 153--159
A. Avron The semantics and proof theory of linear logic . . . . . . . . . . . . . . . . . 161--184 L. Pierre and J.-M. Farinone Rational index of context-free languages in $ \exp (\Theta (\sqrt [p]{n})) $ and $ n^{\Theta ((\ln n)^(1 / p))} $ . . . . 185--204 Y. Velinov An algebraic structure for derivations in rewriting systems . . . . . . . . . . 205--224 O. H. Ibarra and Tao Jiang Relating the power of cellular arrays to their closure properties . . . . . . . . 225--238 G. Duchamp and J. Y. Thibon Transfer theorems for partially commutative polynomials . . . . . . . . 239--249 J.-J. C. Meyer and E. P. de Vink Applications of compactness in the Smyth powerdomain of streams . . . . . . . . . 251--282 M. P. Beal Circular codes, finite automata and entropy . . . . . . . . . . . . . . . . 283--302 K. Hashiguchi Notes on congruence relations and factor pumping conditions for rational languages . . . . . . . . . . . . . . . 303--316 A. Szalas and L. Holenderski Incompleteness of first-order temporal logic with until . . . . . . . . . . . . 317--325 J. W. Grossman and R. S. Zeitman An inherently iterative computation of Ackermann's function . . . . . . . . . . 327--330
D. Arques and J. Francon and M. T. Guichet and P. Guichet Comparison of algorithms controlling concurrent access to a database: A combinatorial approach . . . . . . . . . 3--16 Amir Averbuch and Zvi Galil and Shmuel Winograd Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. Part I. The algebra $G[u]/<Q(u)^\ell>,\ell>1$ . . . 17--56 Allan Borodin and Faith E. Fich and Friedhelm Meyer auf der Heide and Eli Upfal and Avi Wigderson A tradeoff between search and update time for the implicit dictionary problem 57--68 Franz J. Brandenburg On the intersection of stacks and queues 69--80 C. Choffrut and M. P. Schütz\-en\-berger Counting with rational functions . . . . 81--101 Clelia De Felice Finite biprefix sets of paths in a graph 103--128 Juris Hartmanis and Lane A. Hemachandra Complexity classes without machines: On complete languages for UP . . . . . . . 129--142 Peter Kirschenhofer and Helmut Prodinger Further results on digital search trees 143--154 Sarit Kraus and Daniel Lehmann Knowledge, belief and time . . . . . . . 155--174 Klaus-Jörn Lange Decompositions of nondeterministic reductions . . . . . . . . . . . . . . . 175--181 Bjorn Lisper Synthesis and equivalence of concurrent systems . . . . . . . . . . . . . . . . 183--199 Y. Metivier On recognizable subsets of free partially commutative monoids . . . . . 201--208 B. Monien and I. H. Sudborough Min Cut is NP-complete for edge weighted trees . . . . . . . . . . . . . . . . . 209--229 Jean-Pierre Pecuchet Etude syntaxique des parties reconnaissables de mots infinis. (French) [Syntactic study of rational omega-languages of infinite words] . . . 231--248 G. M. Reed and A. W. Roscoe A timed model for communicating sequential processes . . . . . . . . . . 249--261 Louis E. Rosier and Hsu-Chun Yen On the complexity of deciding fair termination of probabilistic concurrent finite-state programs . . . . . . . . . 263--324 Klaus Simon An improved algorithm for transitive closure on acyclic digraphs . . . . . . 325--346 Colin Stirling A generalization of Owicki-Gries's Hoare logic for a concurrent while language 347--359 Howard Straubing Semigroups and languages of dot-depth two . . . . . . . . . . . . . . . . . . 361--378 Peter Varman and Kshitij Doshi An efficient parallel algorithm for updating minimum spanning trees . . . . 379--397
Pier Giorgio Bosco and Elio Giovannetti and Corrado Moiso Narrowing vs. SLD-resolution . . . . . . 3--23 G. Boudol and I. Castellani Concurrency and atomicity . . . . . . . 25--84 Val Breazu-Tannen and Thierry Coquand Extensional models for polymorphism . . 85--114 M. C. Browne and E. M. Clarke and O. Grümberg Characterizing finite Kripke structures in Propositional Temporal Logic . . . . 115--131 Wlodzimierz Drabent and Jan Maluszynski Inductive assertion method for logic programs . . . . . . . . . . . . . . . . 133--155 Y. Lafont The linear abstract machine . . . . . . 157--180 Simona Ronchi Della Rocca Principal type scheme and unification for intersection type discipline . . . . 181--209
Wim H. Hesselink Interpretations of recursion under unbounded nondeterminacy . . . . . . . . 211--234 Wim H. Hesselink Deadlock and fairness in morphisms of transition systems . . . . . . . . . . . 235--257 A. Scottedward Hodel and Michael C. Loui Optimal dynamic embedding of $X$-trees into arrays . . . . . . . . . . . . . . 259--276 K. Kalorkoti The trace invariant and matrix inversion 277--286 Manfred Schmidt-Schauss Implication of clauses is undecidable 287--296 Wojciech Rytter On efficient parallel computations for some dynamic programming problems . . . 297--307 Joost Engelfriet and George Leih Nonterminal bounded NLC graph grammars 309--315 Allen Stoughton Substitution revisited . . . . . . . . . 317--325
I. J. Aalbersberg and G. Rozenberg Theory of traces . . . . . . . . . . . . 1--82 J. Tiuryn and P. Urzyczyn Some relationships between logics of programs and complexity theory . . . . . 83--108
P. America and J. De Bakker Designing equivalent semantic models for process creation . . . . . . . . . . . . 109--176 A. W. Roscoe and C. A. R. Hoare The laws of occam programming . . . . . 177--229
Tali Eilam-Tzoreff and Uzi Vishkin Matching patterns in strings subject to multi-linear transformations . . . . . . 231--254 Jean-Pierre Duval Génération d'une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée. (French) [Generation of a section of conjugation classes and tree of Lyndon words of limited length] 255--283 Arturo Carpi On synchronizing unambiguous automata 285--296 Michael J. Beeson Towards a computation system based on set theory . . . . . . . . . . . . . . . 297--340 Jean-Claude Spehner La reconnaissance des facteurs d'un langage fini dans un texte en temps linéaire. (French) [The recognition of the factors of a finite language in a text in linear time] . . . . . . . . . . 341--381
J. Shallit A generalization of automatic sequences 1--16 P. Domosi and Z. Esik Critical classes for the $\alpha_0$-product . . . . . . . . . . . 17--24 I. Meznik On a subclass of infinity -regular languages . . . . . . . . . . . . . . . 25--32 Xin He A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs . . . . . . . . . . . . . 33--47 C.-J. Seger and J. A. Brzozowski An optimistic ternary simulation of gate races . . . . . . . . . . . . . . . . . 49--66 P. M. van den Broek Comparison of two graph-rewrite systems 67--81 S. Thatte Implementing first-order rewriting with constructor systems . . . . . . . . . . 83--92 R. Cori and E. Sopena and M. Latteux and Y. Roos 2-asynchronous automata . . . . . . . . 93--102
Ronald V. Book and Ding-Zhu Du The structure of generalized complexity cores . . . . . . . . . . . . . . . . . 103--119 Elias Dahlhaus and Marek Karpinski Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs . . . . . . . . . . . . . . 121--136 Tetsuo Moriya and Hideki Yamasaki Accepting conditions for automata on $\omega$-languages . . . . . . . . . . . 137--147 K. N. King Alternating multihead finite automata 149--174 Giuseppe Di Battista and Roberto Tamassia Algorithms for plane representations of acyclic digraphs . . . . . . . . . . . . 175--198 Jay L. Gischer The equational theory of pomsets . . . . 199--224 Werner Alexi Extraction and verification of programs by analysis of formal proofs . . . . . . 225--258 George Gargov and Solomon Passy Determinism and looping in combinatory PDL . . . . . . . . . . . . . . . . . . 259--277 Ludwig Staiger Ein Satz über die Entropie von Untermonoiden. (German) [A theorem on the entropy of submonoids] . . . . . . . 279--282 Thomas Kretschmer A closure property of regular languages 283--287 Andre Arnold Logical definability of fixed points . . 289--297 Edward G. Belaga Bilinear mincing rank . . . . . . . . . 299--306 Nimrod Megiddo and Uzi Vishkin On finding a minimum dominating set in a tournament . . . . . . . . . . . . . . . 307--316 R. Kennaway On 'On graph rewritings' . . . . . . . . 317--320
Serge Abiteboul and R. Hull Restructuring hierarchical database objects . . . . . . . . . . . . . . . . 3--38 Paolo Atzeni and D. Stott Parker Set containment inference and syllogisms 39--65 Edward P. F. Chan and Hector J. Hernandez On the desirability of $\gamma$-acyclic BCNF database schemes . . . . . . . . . 67--104 V. S. Lakshmanan Split-freedom and MVD-intersection: A new characterization of multivalued dependencies having conflict-free covers 105--122 Nancy Lynch and Michael Merritt Introduction to the theory of nested transactions . . . . . . . . . . . . . . 123--185 Domenico Sacca and Carlo Zaniolo The generalized counting method for recursive logic queries . . . . . . . . 187--220 Dirk van Gucht Interaction-free multivalued dependency sets . . . . . . . . . . . . . . . . . . 221--233
Viliam Geffert A representation of a recursively enumerable languages by two homomorphisms and a quotient . . . . . . 235--249 Nageswara S. V. Rao and S. S. Iyengar and R. L. Kashyap An average-case analysis of MAT and inverted file . . . . . . . . . . . . . 251--266 Kai Salomaa A pumping result for $2$-context-free languages . . . . . . . . . . . . . . . 267--287 Thomas Zeugmann On the Power of Recursive Optimizers . . 289--310 Samuel R. Buss and Gyorgy Turan Resolution proofs on generalized pigeonhole principles . . . . . . . . . 311--317 Christoph Meinel The power of nondeterminism in polynomial-size bounded-width branching programs . . . . . . . . . . . . . . . . 319--325
Ursula Schmidt Avoidable patterns on two letters . . . 1--17 M. Livesey Stable families of behavioural equivalences . . . . . . . . . . . . . . 19--41 Klaus Ambos-Spies On the relative complexity of hard problems for complexity classes without complete problems . . . . . . . . . . . 43--61 Seymour Ginsburg and Chang-jie Tang Cohesion of object histories . . . . . . 63--90 J. Howard Johnson A unified framework for disambiguating finite transductions . . . . . . . . . . 91--111
Masami Hagiya Generalization from partial parametrization in higher-order type theory . . . . . . . . . . . . . . . . . 113--139 Jean-Camille Birget Concatenation of inputs in a two-way automaton . . . . . . . . . . . . . . . 141--156 Clelia de Felice Construction of a family of finite maximal codes . . . . . . . . . . . . . 157--184 Andrzej Pelc Searching with known error probability 185--202 Juraj Hromkovic Tradeoffs for language recognition on alternating machines . . . . . . . . . . 203--221 Takashi Saito and Hidenosuke Nishio Structural and behavioral equivalence relations in automata networks . . . . . 223--237
Ding-Zhu Du and Ronald V. Book On inefficient special cases of NP-complete problems . . . . . . . . . . 239--252 Georges Gardarin and Irene Guessarian and Christophe de Maindreville Translation of logic programs into functional fixpoint equations . . . . . 253--274 David B. Benson and Jerzy Tiuryn Fixed points in free process algebras, part I . . . . . . . . . . . . . . . . . 275--294 Andrzej Lingas Subgraph isomorphism for biconnected outerplanar graphs in cubic time . . . . 295--302 Stephen L. Bloom and Zoltan Esik Equational logic of circular data type specification . . . . . . . . . . . . . 303--331 Aldo de Luca and Stefano Varricchio Some combinatorial properties of the Thue--Morse sequence and a problem in semigroups . . . . . . . . . . . . . . . 333--348
Hans-Jörg Stoss On the representation of rational functions of bounded complexity . . . . 1--13 Hans-Jörg Stoss Lower bounds for the complexity of polynomials . . . . . . . . . . . . . . 15--23 K. Jojczyk and J. Konieczny and T. Kuzak On interleaving behaviour of PT-nets . . 25--38 Etsuji Tomita and Kazushi Seino A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is real-time strict . . . . . . 39--53 Hiroyuki Sato E-CCC: between CCC and TOPOS . . . . . . 55--66 Dang Van Hung and Elod Knuth Semi-commutations and Petri nets . . . . 67--81 Eli Shamir and Assaf Schuster Communication aspects of networks based on geometric incidence relations . . . . 83--96 J. Roger Hindley BCK-combinators and linear \$lambda@-terms have types . . . . . . . 97--105 Zvi Galil and Raffaele Giancarlo Speeding up dynamic programming with applications to molecular biology . . . 107--118 Marco Protasi and Maurizio Talamo On the number of arithmetical operations for finding Fibonacci numbers . . . . . 119--124 E. Korach and S. Moran and S. Zaks Optimal lower bounds for some distributed algorithms for a complete network of processors . . . . . . . . . 125--132
Clyde P. Kruskal and Larry Rudolph and Marc Snir Techniques for parallel manipulation of sparse matrices . . . . . . . . . . . . 135--157 Yves Robert and Denis Trystram Optimal scheduling algorithms for parallel Gaussian elimination . . . . . 159--173 Gordon Lyon Design factors for parallel processing benchmarks . . . . . . . . . . . . . . . 175--189 J. C. Bermond and J. M. Fourneau Independent connections: An easy characterization of baseline-equivalent multistage interconnection networks . . 191--201 I. F. Akyildiz and H. von Brand Exact solutions for open, closed and mixed queueing networks with rejection blocking . . . . . . . . . . . . . . . . 203--219
Eugene W. Stark Concurrent transition systems . . . . . 221--269 Denis Therien Programs over aperiodic monoids . . . . 271--280 Antoni Mazurkiewicz and Edward Ochmanski and Wojciech Penczek Concurrent systems and inevitability . . 281--304 Rodney R. Howell and Louis E. Rosier Problems concerning fairness and temporal logic for conflict-free Petri nets . . . . . . . . . . . . . . . . . . 305--329 Noga Alon and Uri Zwick On Neciporuk's theorem for branching programs . . . . . . . . . . . . . . . . 331--342 Hans Kleine Büning and Theodor Lettmann and Ernst W. Mayr Projections of vector addition system reachability sets are semilinear . . . . 343--350
Patrice Enjalbert and Luis Farinas del Cerro Modal resolution in clausal form . . . . 1--33 Martin Abadi The power of temporal proofs . . . . . . 35--83 Satish R. Thatte Full abstraction and limiting completeness in equational languages . . 85--119
Anonymous Conference on Arithmetics and Coding Systems . . . . . . . . . . . . . . . . ?? Jean-Paul Allouche On a sequence of rational functions . . 123--130 F. Blanchard \$beta@-expansions and symbolic dynamics 131--141 Noelle Bleuzen-Guernalec On a possible classification of real-time constructed sequences . . . . 143--148 F. M. Dekking On the probability of occurrence of labelled subtrees of a randomly labelled tree . . . . . . . . . . . . . . . . . . 149--152 J.-M. Dumont and Alain Thomas Systémes de num\-é\-ra\-tion et fonction fractales relatifs aux substitutions. (French) [Systems of numeration and fractal functions relative to substitutions] . . . . . . . . . . . . . 153--169 G. Hansel and D. Perrin Rational probability measures . . . . . 171--188 P. Hellekalek and G. Larcher On Weyl sums and skew products over irrational rotations . . . . . . . . . . 189--196 Cor Kraaikamp Statistic and ergodic properties of Minkowski's diagonal continued fraction 197--212 M. Mendes France and A. J. van der Poorten From geometry to Euler identities . . . 213--220 Filippo Mignosi Infinite words with linear subword complexity . . . . . . . . . . . . . . . 221--242 Makoto Mori On the Fredholm determinant of a piecewise linear transformation . . . . 243--248 Brigitte Mosse Q-Adic spectral analysis of some arithmetic sequences . . . . . . . . . . 249--263 Antonio Restivo Finitely generated sofic systems . . . . 265--270
Hirofumi Yokouchi Church--Rosser theorem for a rewriting system on categorical combinators . . . 271--290 Therese Hardin Confluence results for the pure strong categorical logic CCL \$lambda@-calculi as subsystems of {CCL} . . . . . . . . . 291--342 J. C. Shepherdson A sound and complete semantics for a version of negation as failure . . . . . 343--371
T. Lehmkuhl and T. Lickteig On the order of approximation in approximative triadic decompositions of tensors . . . . . . . . . . . . . . . . 1--14 P. E. Dunne On monotone simulations of nonmonotone networks . . . . . . . . . . . . . . . . 15--25 A. Piperno Abstraction problems in combinatory logic: a compositive approach . . . . . 27--43 J. Kari Observations concerning a public-key cryptosystem based on iterated morphisms 45--53 Zhang Luo Xin An efficient algorithm to decide whether a monoid presented by a regular Church--Rosser Thue system is a group 55--63 R. op den Akker On LC(0) grammars and languages . . . . 65--85 A. Urquhart The complexity of Gentzen systems for propositional logic . . . . . . . . . . 87--97 R. Statman On sets of solutions to combinator equations . . . . . . . . . . . . . . . 99--104 A. Pelc Weakly adaptive comparison searching . . 105--111 D. Mundici Functions computed by monotone Boolean formulas with no repeated variables . . 113--114
Volker Diekert On the Knuth--Bendix completion for concurrent processes . . . . . . . . . . 117--136 Martin Dietzfelbinger Lower bounds for sorting of sums . . . . 137--155 Herbert Edelsbrunner and Guenter Rote and Ermo Welzl Testing the necklace condition for shortest tours and optimal factors in the plane . . . . . . . . . . . . . . . 157--180 Christos Levcopoulos and Andrzej Lingas and Jorg-R. R. Sack Heuristics for optimum binary search trees and minimum weight triangulation problems . . . . . . . . . . . . . . . . 181--203 M. A. Nait Abdallah A logico-algebraic approach to the model theory of knowledge . . . . . . . . . . 205--232
P. Weil Inverse monoids of dot-depth two . . . . 233--245 H. Yamasaki Language-theoretical representations of $Gw$-languages . . . . . . . . . . . . . 247--254 D. Angluin and W. I. Gasarch and C. H. Smith Training sequences . . . . . . . . . . . 255--272 A. Ito and K. Inoue and I. Takanami Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180 degrees-rotation . . . . . . . . . . . . 273--287 G. Jacopini and P. Mentrasti Generation of invertible functions . . . 289--297 J. A. Makowsky and I. Sain Weak second order characterizations of various program verification systems . . 299--321 M. Mezghiche On pseudo-c beta normal form in combinatory logic . . . . . . . . . . . 323--331 M. Tiomkin Probabilistic termination versus fair termination . . . . . . . . . . . . . . 333--340 J. Honkala A necessary condition for the rationality of the zeta function of a regular language . . . . . . . . . . . . 341--347
Charles Swart and Dana Richards On the inference of strategies . . . . . 5--18 Friedrich Otto On deciding confluence of finite string-rewriting systems modulo partial commutativity . . . . . . . . . . . . . 19--35 Ursula Martin A geometrical approach to multiset orderings . . . . . . . . . . . . . . . 37--54 Michael Clausen Fast generalized Fourier transforms . . 55--63 Daniele Beauquier Minimal automation for a factorial, transitive, and rational language . . . 65--73 Etsuro Moriya A grammatical characterization of alternating pushdown automata . . . . . 75--85 G. Marongiu and S. Tulipani On a conjecture of Bergstra and Tucker 87--97 Katsushi Inoue and Itsuo Takanami and Juraj Hromkovic Leaf-size hierarchy of two-dimensional alternating Turing machines . . . . . . 99--110 Dana Pardubska and Ivana Stefanekova Nondeterministic multicounter machines and complementation . . . . . . . . . . 111--113 M. Cosnard and J. Duprat and A. Ferreira Complexity of selection in X + Y . . . . 115--120 Catherine Petuaud Entropie topologique des syst\`emes specifiés. (French) [Topological entropy of specified systems] . . . . . . . . . 121--128 Ramon Pino Perez Decidability of the restriction equational theory in the partial lambda calculus . . . . . . . . . . . . . . . . 129--139
K. Madlener and F. Otto About the descriptive power of certain classes of finite string-rewriting systems . . . . . . . . . . . . . . . . 143--172 L. Bachmair and N. Dershowitz Completion for rewriting modulo a congruence . . . . . . . . . . . . . . . 173--201 J. H. Gallier and W. Snyder Complete sets of transformations for general E-unification . . . . . . . . . 203--260 C. Choppy and S. Kaplan and M. Soria Complexity analysis of term-rewriting systems . . . . . . . . . . . . . . . . 261--282 J. C. M. Baeten and J. A. Bergstra and J. W. Klop and W. P. Weijland Term-rewriting systems with rule priorities . . . . . . . . . . . . . . . 283--301 H. Kirchner Schematization of infinite sets of rewrite rules generated by divergent completion processes . . . . . . . . . . 303--332
P. Kirschenhofer and H. Prodinger and W. Szpankowski On the balance property of Patricia trees: external path length viewpoint 1--17 J. H. Chang and O. H. Ibarra and M. A. Palis Efficient simulations of simple models of parallel computation by time-bounded ATMs and space-bounded TMs . . . . . . . 19--36 M. Droste Event structures and domains . . . . . . 37--47 G. Hofer Left ideals and reachability in machines 49--56 G. Gambosi and G. F. Italiano and M. Talamo Worst-case analysis of the set-union problem with extended backtracking . . . 57--70 U. Huckenbeck Euclidian geometry in terms of automata theory . . . . . . . . . . . . . . . . . 71--87 H. J. Karloff An NC algorithm for Brooks' theorem . . 89--103 M. B. Josephs The semantics of lazy functional languages . . . . . . . . . . . . . . . 105--111 B. S. Chlebus A hierarchy of propositional Horn formulas . . . . . . . . . . . . . . . . 113--119
V. Arvind and S. Biswas On some bandwidth restricted versions of the satisfiability problem of propositional CNF formulas . . . . . . . 123--134 H. A. Blair and V. S. Subrahmanian Paraconsistent logic programming . . . . 135--154 A. Lingas and A. Proskurowski On parallel complexity of the subgraph homeomorphism and the subgraph isomorphism problem for classes of planar graphs . . . . . . . . . . . . . 155--173 J. Parrow Submodule construction as equation solving in CCS . . . . . . . . . . . . . 175--202 R. Ramanujam Semantics of distributed definite clause programs . . . . . . . . . . . . . . . . 203--220
T. Coquand Categories of embeddings . . . . . . . . 221--237 R. Gutbrod A transformation system for generating description languages of chain code pictures . . . . . . . . . . . . . . . . 239--252 F. Blanchard Certain sofic systems engendered codes 253--265 N. Immerman and S. R. Mahaney Relativizing relativized computations 267--276 M. T. Hortala-Gonzalez and M. Rodriguez-Artalejo Hoare's logic for nondeterministic regular programs: a nonstandard approach 277--302 F. Bracho Continuously generated fixed points . . 303--317 P. Narendran and F. Otto Some polynomial-time algorithms for finite monadic Church--Rosser Thue systems . . . . . . . . . . . . . . . . 319--332 U. Solitro A typed calculus based on a fragment of linear logic . . . . . . . . . . . . . . 333--342 E. Gafni and J. Naor and P. Ragde On separating the EREW and CREW PRAM models . . . . . . . . . . . . . . . . . 343--346 C. P. Rupert Comment on a remark of Forys . . . . . . 347--348
L. Vieille Recursive query processing: the power of logic . . . . . . . . . . . . . . . . . 1--53 J.-M. Kerisit A relational approach to logic programming: the extended Alexander method . . . . . . . . . . . . . . . . . 55--68 S. Kaplan Algebraic specification of concurrent systems . . . . . . . . . . . . . . . . 69--115
F. Nielson Two-level semantics and abstract interpretation . . . . . . . . . . . . . 117--242
M. Felleisen and D. P. Friedman A syntactic theory of sequential state 243--287 M. Falaschi and G. Levi and C. Palamidessi and M. Martelli Declarative modeling of the operational behavior of logic languages . . . . . . 289--318 K. A. Baker and G. F. McNulty and W. Taylor Growth problems for avoidable words . . 319--345
Marek Chrobak Errata to: ``Finite Automata and Unary Languages'': [Theoret. Comput. Sci. 47 (1986) 149--158] . . . . . . . . . . . . 497--498