| 1985 | A fast heuristic for covering polygons by rectangles. Christos Levcopoulos |
| 1985 | A language theoretic approach to serialization problem in concurrent systems. Marie-Paule Flé, Gérard Roucairol |
| 1985 | A lower bound on the oscillation complexity of context-free languages. Thomas Gundermann |
| 1985 | A multiparameter analysis of the boundedness problem for vector addition systems. Louis E. Rosier, Hsu-Chun Yen |
| 1985 | A quadratic regularity test for non-deleting macro S grammars. Helmut Seidl |
| 1985 | A unifying theorem for algebraic semantics and dynamic logics. Hajnal Andréka, Irène Guessarian, István Németi |
| 1985 | About two-way transducers. Brigitte Rozoy |
| 1985 | Algorithms solving path systems. Bogdan S. Chlebus |
| 1985 | Are lower bounds on the complexity lower bounds for universal circuits. R. G. Nigmatullin |
| 1985 | Array processing machines. Jan van Leeuwen, Jirí Wiedermann |
| 1985 | Clustering to minimize the sum of volumes of convex hulls of clusters is NP-complete. Mirko Krivánek, Jaroslav Morávek |
| 1985 | Continuous abstract data types: basic machinery and results. Andrzej Tarlecki, Martin Wirsing |
| 1985 | Decidability of confluence for ground term rewriting systems. Max Dauchet, Sophie Tison |
| 1985 | Degeneration of Shimura surfaces and a problem in coding theory. Th. Zink |
| 1985 | Depth efficient transformations of arithmetic into Boolean circuits. Hermann Jung |
| 1985 | Discrete extremal problems on covering. A. D. Korshunov |
| 1985 | Elements of a general theory of combinatorial structures. Philippe Flajolet |
| 1985 | Enumerative combinatorics and algebraic languages. Gérard Viennot |
| 1985 | Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic. Alexander L. Chistov |
| 1985 | Fast parallel vertex colouring. Frank Bauernöppel, Hermann Jung |
| 1985 | Free cost measures of trees. Rainer Kemp |
| 1985 | Fundamentals of Computation Theory, FCT '85, Cottbus, GDR, September 9-13, 1985 Lothar Budach |
| 1985 | Generalized Thue-Morse sequences. Patrice Séébold |
| 1985 | Intersecting two polyhedra one of which is convex. Kurt Mehlhorn, Klaus Simon |
| 1985 | Iterated linear control and iterated one-turn pushdowns. Heiko Vogler |
| 1985 | Linear comparison complexity of the n-cube membership problem. Mirko Krivánek, Jaroslav Morávek |
| 1985 | Logic programming and substitutions. Gudmund Skovbjerg Frandsen |
| 1985 | Lower bounds for Boolean formulae of depth 3 and the topology of the n-cube (preliminary version). Klaus Kriegel, Stephan Waack |
| 1985 | Lower bounds on the complexity of 1-time only branching programs. Paul E. Dunne |
| 1985 | Muller automata and bi-infinite words. Danièle Beauquier |
| 1985 | On colour critical graphs. Horst Sachs |
| 1985 | On coordinated rewriting. Andrzej Ehrenfeucht, Hendrik Jan Hoogeboom, Grzegorz Rozenberg |
| 1985 | On formal languages, probabilities, paging and decoding algorithms. Joffroy Beauquier, Loÿs Thimonier |
| 1985 | On several kinds of space-bounded on-line multicounter automata. Lutz Voelkel |
| 1985 | On some "non-uniform" complexity measures. José L. Balcázar, Josep Díaz, Joaquim Gabarró |
| 1985 | On some topological properties of logic programs. M. A. Nait Abdallah |
| 1985 | On the Boolean closure of NP. Gerd Wechsung |
| 1985 | On the decidability of the theory of free groups (in Russian) = К Вопросу О Раэрещимости Теории Свободной Группы. G. S. Makanin |
| 1985 | On the length of single dynamic tests for monotone Boolean functions. Valery A. Vardanian |
| 1985 | On the restriction of some NP-complete graph problems to permutation graphs. Andreas Brandstädt, Dieter Kratsch |
| 1985 | Parallel algorithms for connected components in a graph. Václav Koubek, Jana Krsnakova |
| 1985 | Parallel time O(log n) recognition of unambiguous CFLs. Wojciech Rytter |
| 1985 | Partial ordering derivations for CCS. Pierpaolo Degano, Rocco De Nicola, Ugo Montanari |
| 1985 | Probabilistic algorithms in group theory. John H. Reif |
| 1985 | Products of group languages. Stuart W. Margolis, Jean-Eric Pin |
| 1985 | Quantifiers in combinatory PDL: completeness, definability, incompleteness. Solomon Passy, Tinko Tinchev |
| 1985 | Recent results on codes. Christophe Reutenauer |
| 1985 | Recent results on continuous ordered algebras. Evelyn Nelson |
| 1985 | Space complexity of alternating Turing machines. Maris Alberts |
| 1985 | Statistical testing of finite sequences based on algorithmic complexity. Ivan Kramosil |
| 1985 | String grammars with disconnecting. Klaus-Jörn Lange, Emo Welzl |
| 1985 | The complexity of embedding graphs into binary trees. Burkhard Monien |
| 1985 | The critical complexity of all (monotone) Boolean functions and monotone graph properties. Ingo Wegener |
| 1985 | Tree-partite graphs and the complexity of algorithms. Detlef Seese |