Acta Informatica

2005

Type-based hot swapping of running modules
by: Dominic Duggan v. 41 i. 4-5 p. 181 - 220
A deterministic skip list for k-dimensional range search
by: Michael G. Lamoureux, Bradford G. Nickerson v. 41 i. 4-5 p. 221 - 255
Hybrid networks of evolutionary processors are computationally complete
by: Erzsébet Csuhaj-Varjú, Carlos Martín-Vide, Victor Mitrana v. 41 i. 4-5 p. 257 - 272
Fast allocation and deallocation with an improved buddy system
by: Gerth Stølting Brodal, Erik D. Demaine, J. Ian Munro v. 41 i. 4-5 p. 273 - 291
Families of automata characterizing context-sensitive languages
by: Christophe Morvan, Chloe Rispal v. 41 i. 4-5 p. 293 - 314
Preemptive online algorithms for scheduling with machine cost
by: Yiwei Jiang, Yong He v. 41 i. 6 p. 315 - 340
Optimal recovery schemes in fault tolerant distributed computing
by: Kamilla Klonowska, Håkan Lennerstad, Lars Lundberg, Charlie Svahnberg v. 41 i. 6 p. 341 - 365
On the complexity of deciding typability in the relational algebra
by: Stijn Vansummeren v. 41 i. 6 p. 367 - 381

2004

A new natural structural congruence in the pi-calculus with replication
by: Joost Engelfriet, Tjalling Gelsema v. 40 i. 6-7 p. 385 - 430
Past is for free: on the complexity of verifying linear temporal properties with past
by: Nicolas Markey v. 40 i. 6-7 p. 431 - 458
Reducing non-determinism in right nulled GLR parsers
by: Elizabeth Scott, Adrian Johnstone v. 40 i. 6-7 p. 459 - 489
Trajectory-based codes
by: Michael Domaratzki v. 40 i. 6-7 p. 491 - 527
Program reversals for evolutions with non-uniform step costs
by: Andrea Walther v. 40 i. 4 p. 235 - 263
Specification transformers: a predicate transformer approach to composition
by: Michel Charpentier, K. Mani Chandy v. 40 i. 4 p. 265 - 301
A bi-criterion single-machine scheduling problem with learning considerations
by: Wen-Chiung Lee, Chin-Chia Wu, Hua-Jung Sung v. 40 i. 4 p. 303 - 315
Timed automata with urgent transitions
by: Roberto Barbuti, Luca Tesei v. 40 i. 5 p. 317 - 347
Self-embedded context-free grammars with regular counterparts
by: Stefan Andrei, Wei-Ngan Chin, Salvador Valerio Cavadini v. 40 i. 5 p. 349 - 365
Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines
by: Yong He, Yiwei Jiang v. 40 i. 5 p. 367 - 383
On the equivalence and rewriting of aggregate queries
by: Stéphane Grumbach, Maurizio Rafanelli, Leonardo Tininini v. 40 i. 8 p. 529 - 584
Exhaustive generation of combinatorial objects by ECO
by: Silvia Bacchelli, Elena Barcucci, Elisabetta Grazzini, Elisa Pergola v. 40 i. 8 p. 585 - 602
On the complexity of drawing trees nicely: corrigendum
by: Thorsten Akkerman, Christoph Buchheim, Michael Jünger, Daniel Teske v. 40 i. 8 p. 603 - 607
Self-stabilizing group communication in directed networks
by: Shlomi Dolev, Elad Schiller v. 40 i. 9 p. 609 - 636
On best transitive approximations to simple graphs
by: Steven Delvaux, Leon Horsten v. 40 i. 9 p. 637 - 655
Approximation schemes for the Min-Max Starting Time Problem
by: Leah Epstein, Tamir Tassa v. 40 i. 9 p. 657 - 674
Maintaining mobile transactional consistency in hybrid broadcast environments
by: SungSuk Kim, Sun Ok Yang, SangKeun Lee v. 41 i. 2-3 p. 65 - 81
Project scheduling with irregular costs: complexity, approximability, and algorithms
by: Alexander Grigoriev, Gerhard J. Woeginger v. 41 i. 2-3 p. 83 - 97
Limit laws for terminal nodes in random circuits with restricted fan-out: a family of graphs generalizing binary search trees
by: Hosam M. Mahmoud, Tatsuie Tsukiji v. 41 i. 2-3 p. 99 - 110
Trading polarizations for labels in P systems with active membranes
by: Artiom Alhazov, Linqiang Pan, Gheorghe Paun v. 41 i. 2-3 p. 111 - 144
P systems with symport/antiport simulating counter automata
by: Pierluigi Frisco, Hendrik Jan Hoogeboom v. 41 i. 2-3 p. 145 - 170
Three-element codes with one d-primitive word
by: Zheng-Zhu Li, Y. S. Tsai v. 41 i. 2-3 p. 171 - 180
Random sprouts as internet models, and Pólya processes
by: Hosam M. Mahmoud v. 41 i. 1 p. 1 - 18
An axiomatization of graphs
by: Symeon Bozapalidis, Antonios Kalampakas v. 41 i. 1 p. 19 - 61
Erratum: The size of random bucket trees via urn models
by: Hosam M. Mahmoud v. 41 i. 1 p. 63 - 63

2003

Adding inclusion dependencies to an object-oriented data model with uniqueness constraints
by: Joachim Biskup, Torsten Polle v. 39 i. 6-7 p. 391 - 449
A word on 7 letters which is non-repetitive up to mod 5
by: James D. Currie, Erica Moodie v. 39 i. 6-7 p. 451 - 468
Strong bisimilarity of simple process algebras: complexity lower bounds
by: Jirí Srba v. 39 i. 6-7 p. 469 - 499
Structural operational semantics and bounded nondeterminism
by: Wan Fokkink, Thuy Duong Vu v. 39 i. 6-7 p. 501 - 516
Networks of evolutionary processors
by: Juan Castellanos, Carlos Martín-Vide, Victor Mitrana, Jose M. Sempere v. 39 i. 6-7 p. 517 - 529
A top-down proof procedure for generalized data dependencies
by: Stéphane Coulondre v. 39 i. 1 p. 1 - 29
Synchronized regular expressions
by: Giuseppe Della Penna, Benedetto Intrigila, Enrico Tronci, Marisa Venturini Zilli v. 39 i. 1 p. 31 - 70
A functional approach for temporal × modal logics
by: Alfredo Burrieza, Inman P. de Guzmán v. 39 i. 2 p. 71 - 96
Bin stretching revisited
by: Leah Epstein v. 39 i. 2 p. 97 - 117
Stochastic cooperative distributed grammar systems and random graphs
by: Ján Gaso, Martin Nehéz v. 39 i. 2 p. 119 - 140
Edsger W. Dijkstra - Acta Informatica and Marktoberdorf
by: Friedrich L. Bauer, Manfred Broy v. 39 i. 3 p. 141 - 142
Fundamentals of control flow in workflows
by: Bartek Kiepuszewski, Arthur H. M. ter Hofstede, Wil M. P. van der Aalst v. 39 i. 3 p. 143 - 209
Preference rankings in the face of uncertainty
by: Wim H. Hesselink v. 39 i. 3 p. 211 - 231
Stepwise development of fair distributed systems
by: Axel Wabenhorst v. 39 i. 4 p. 233 - 271
On Gurevich's theorem on sequential algorithms
by: Wolfgang Reisig v. 39 i. 4 p. 273 - 305
Coincidental extension of scattered context languages
by: Alexander Meduna v. 39 i. 5 p. 307 - 314
Reasoning about probabilistic sequential programs in a probabilistic logic
by: Mingsheng Ying v. 39 i. 5 p. 315 - 389
Towards action refinement for true concurrent real time
by: Mila E. Majster-Cederbaum, Jinzhao Wu v. 39 i. 8 p. 531 - 577
A note on pure and p-pure languages
by: Pedro V. Silva v. 39 i. 8 p. 579 - 595
Ideal preemptive schedules on two processors
by: Edward G. Coffman Jr., Jay Sethuraman, Vadim G. Timkovsky v. 39 i. 8 p. 597 - 612
A comparison of pebble tree transducers with macro tree transducers
by: Joost Engelfriet, Sebastian Maneth v. 39 i. 9 p. 613 - 698
Erratum: Coincidental extension of scattered context languages
by: Alexander Meduna v. 39 i. 9 p. 699 - 699
Extending the accommodating function
by: Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen v. 40 i. 1 p. 3 - 35
Pipelines: Modelling a software architecture through relations
by: Ernst-Erich Doberkat v. 40 i. 1 p. 37 - 79
Element distinctness on one-tape Turing machines: a complete solution
by: Amir M. Ben-Amram, Omer Berkman, Holger Petersen v. 40 i. 2 p. 81 - 94
Canonical prefixes of Petri net unfoldings
by: Victor Khomenko, Maciej Koutny, Walter Vogler v. 40 i. 2 p. 95 - 118
Sticky-free and overhang-free DNA languages
by: Lila Kari, Stavros Konstantinidis, Elena Losseva, Geoff Wozniak v. 40 i. 2 p. 119 - 157
Providing view synchrony for group communication services
by: Nicole Lesley, Alan Fekete v. 40 i. 3 p. 159 - 210
A distributed QoS-Aware multicast routing protocol
by: Li Layuan, Li Chunlin v. 40 i. 3 p. 211 - 233

2002

Comparing the worst-case efficiency of asynchronous systems with PAFAS
by: Flavio Corradini, Walter Vogler, Lars Jenner v. 38 i. 11/12 p. 735 - 792
Gray visiting Motzkins
by: Vincent Vajnovszki v. 38 i. 11/12 p. 793 - 811
The size of random bucket trees via urn models
by: Hosam M. Mahmoud v. 38 i. 11/12 p. 813 - 838
On the complexity of the identification problem in Hamming spaces
by: Iiro S. Honkala, Antoine Lobstein v. 38 i. 11/12 p. 839 - 845
A quadratic speedup theorem for iterative arrays
by: Chuzo Iwamoto, Katsuyuki Tateishi, Kenichi Morita, Katsunobu Imai v. 38 i. 11/12 p. 847 - 858
Minimally adequate teacher synthesizes statechart diagrams
by: Erkki Mäkinen, Tarja Systä v. 38 i. 4 p. 235 - 259
The variance of the height of digital search trees
by: Michael Drmota v. 38 i. 4 p. 261 - 276
Axiomatising timed automata
by: Huimin Lin, Wang Yi v. 38 i. 4 p. 277 - 305
Impurity measures in databases
by: Dan A. Simovici, Dana Cristofor, Laurentiu Cristofor v. 38 i. 5 p. 307 - 324
Containment and disjointedness in partitioned normal form relations
by: Jixue Liu, Millist W. Vincent v. 38 i. 5 p. 325 - 342
An assertional criterion for atomicity
by: Wim H. Hesselink v. 38 i. 5 p. 343 - 366
Object type constructors
by: Dominic Duggan v. 38 i. 6 p. 367 - 408
Words, univalent factors, and boxes
by: Arturo Carpi, Aldo de Luca, Stefano Varricchio v. 38 i. 6 p. 409 - 436
Deriving and paraphrasing information grammars using object-oriented analysis models
by: Paul J. M. Frederiks, Theo P. van der Weide v. 38 i. 7 p. 437 - 488
A general procedure to check conjunctive query containment
by: Miguel R. Penabad, Nieves R. Brisaboa, Héctor J. Hernández, José R. Paramá v. 38 i. 7 p. 489 - 529
Automatic verification of concurrent systems using a formula-based compositional approach
by: Antonella Santone v. 38 i. 8 p. 531 - 564
Relaxed red-black trees with group updates
by: Kim S. Larsen v. 38 i. 8 p. 565 - 586
On the non-approximability of points-to analysis
by: Venkatesan T. Chakaravarthy, Susan Horwitz v. 38 i. 8 p. 587 - 598
Bases for closed sets of implicants and implicates in temporal logic
by: Pablo Cordero, Manuel Enciso, Inman P. de Guzmán v. 38 i. 9 p. 599 - 619
Adding a path connectedness operator to FO+poly (linear)
by: Chris Giannella, Dirk Van Gucht v. 38 i. 9 p. 621 - 648
Formal properties of XML grammars and languages
by: Jean Berstel, Luc Boasson v. 38 i. 9 p. 649 - 671
Packing rectangles in a strip
by: Edward G. Coffman Jr., Peter J. Downey, Peter M. Winkler v. 38 i. 10 p. 673 - 693
Membrane systems with promoters/inhibitors
by: Paolo Bottoni, Carlos Martín-Vide, Gheorghe Paun, Grzegorz Rozenberg v. 38 i. 10 p. 695 - 720
Generalized normal form for rewriting P systems
by: Mutyam Madhu, Kamala Krithivasan v. 38 i. 10 p. 721 - 734

2001

Letter from the Editor
by: Manfred Broy v. 37 i. 4/5 p. 227 - 228
Refinement of actions and equivalence notions for concurrent systems
by: Rob J. van Glabbeek, Ursula Goltz v. 37 i. 4/5 p. 229 - 327
Demonic, angelic and unbounded probabilistic choices in sequential programs
by: Annabelle McIver, Carroll Morgan v. 37 i. 4/5 p. 329 - 354
Analysis of range search for random k-d trees
by: Philippe Chanzy, Luc Devroye, Carlos Zamora-Cura v. 37 i. 4/5 p. 355 - 383
Recursion and Petri nets
by: Eike Best, Raymond R. Devillers, Maciej Koutny v. 37 i. 11-12 p. 781 - 829
Labelled transition logic: an outline
by: Egidio Astesiano, Gianna Reggio v. 37 i. 11-12 p. 831 - 879
A Markov modulated multi-server queue with negative customers - The MM CPP/GE/c/L G-queue
by: Ram Chakka, Peter G. Harrison v. 37 i. 11-12 p. 881 - 919
A sequential real-time refinement calculus
by: Ian J. Hayes, Mark Utting v. 37 i. 6 p. 385 - 448
Synchronized extension systems
by: Ferucio Laurentiu Tiplea, Erkki Mäkinen, Corina Apachite v. 37 i. 6 p. 449 - 465
`Closed Interval Process Algebra' versus `Interval Process Algebra'
by: Flavio Corradini, Marco Pistore v. 37 i. 7 p. 467 - 509
Parallel communicating grammar systems with terminal transmission
by: Henning Fernau v. 37 i. 7 p. 511 - 540
A theory of bunches
by: Joseph M. Morris, Alexander Bunkenburg v. 37 i. 8 p. 541 - 561
A construction of distributed reference counting
by: Luc Moreau, Jean Duprat v. 37 i. 8 p. 563 - 595
Periodic-like words, periodicity, and boxes
by: Arturo Carpi, Aldo de Luca v. 37 i. 8 p. 597 - 618
Efficient recognition algorithms for boundary and linear eNCE graph languages
by: Changwook Kim v. 37 i. 9 p. 619 - 632
Even faster generalized LR parsing
by: John Aycock, R. Nigel Horspool, Jan Janousek, Borivoj Melichar v. 37 i. 9 p. 633 - 651
On the tree inclusion problem
by: Laurent Alonso, René Schott v. 37 i. 9 p. 653 - 670
Yet another generation of LALR parsers for regular right part grammars
by: Shin-ichi Morimoto, Masataka Sassa v. 37 i. 9 p. 671 - 697
Extending stratified datalog to capture complexity classes ranging from P to QH
by: Sergio Greco, Domenico Saccà, Carlo Zaniolo v. 37 i. 10 p. 699 - 725
Running a job on a collection of partly available machines, with on-line restarts
by: Rob van Stee, Johannes A. La Poutré v. 37 i. 10 p. 727 - 742
Relaxed balance for search trees with local rebalancing
by: Kim S. Larsen, Thomas Ottmann, Eljas Soisalon-Soininen v. 37 i. 10 p. 743 - 763
A polynomial time computable metric between point sets
by: Jan Ramon, Maurice Bruynooghe v. 37 i. 10 p. 765 - 780
Category-theoretic fibration as an abstraction mechanism in information systems
by: Robert M. Colomb, Christopher N. G. Dampney, Michael Johnson v. 38 i. 1 p. 1 - 44
Correctness of dataflow and systolic algorithms using algebras of streams
by: Karl Meinke, L. J. Steggles v. 38 i. 1 p. 45 - 88
Timed tree automata with an application to temporal logic
by: Salvatore La Torre, Margherita Napoli v. 38 i. 2 p. 89 - 116
Group weighted finite transducers
by: Masami Ito, Carlos Martín-Vide, Victor Mitrana v. 38 i. 2 p. 117 - 129
Tree-systems of morphisms
by: Jürgen Dassow, Gheorghe Paun, Gabriel Thierrin, Sheng Yu v. 38 i. 2 p. 131 - 153
Process algebra with action dependencies
by: Arend Rensink, Heike Wehrheim v. 38 i. 3 p. 155 - 234

2000

Single Machine Scheduling with Deadlines and Increasing Rates of Processing Times
by: T. C. Edwin Cheng, Q. Ding v. 36 i. 9/10 p. 673 - 692
Data Refinement and Algebraic Structure
by: Yoshiki Kinoshita, John Power v. 36 i. 9/10 p. 693 - 719
Minimal Huffman Trees
by: Gunnar Forst, Anders Thorup v. 36 i. 9/10 p. 721 - 734
Analytic Variations on Bucket Selection and Sorting
by: Hosam M. Mahmoud, Philippe Flajolet, Philippe Jacquet, Mireille Régnier v. 36 i. 9/10 p. 735 - 760
Abstraction and Performance in the Design of Parallel Programs: An Overview of the SAT Approach
by: Sergei Gorlatch, Christian Lengauer v. 36 i. 9/10 p. 761 - 803
On Slender 0L Languages over the Binary Alphabet
by: Juha Honkala v. 36 i. 9/10 p. 805 - 815
On the Generalization of Higman and Kruskal's Theorems to Regular Languages and Rational Trees
by: Benedetto Intrigila, Stefano Varricchio v. 36 i. 9/10 p. 817 - 835
Querying Sequence Databases with Transducers
by: Anthony J. Bonner, Giansalvatore Mecca v. 36 i. 7 p. 511 - 544
How to Calculate Symmetries of Petri Nets
by: Karsten Schmidt v. 36 i. 7 p. 545 - 590
Specifying Communication in Distributed Information Systems
by: Hans-Dieter Ehrich, Carlos Caleiro v. 36 i. 8 p. 591 - 616
A Complete Algebraic Characterization of Behavioral Subtyping
by: Gary T. Leavens, Don Pigozzi v. 36 i. 8 p. 617 - 663
On the Expressiveness of Subset-Sum Representations
by: Lucian Ilie, Arto Salomaa v. 36 i. 8 p. 665 - 672
Verification of Clocked and Hybrid Systems
by: Yonit Kesten, Zohar Manna, Amir Pnueli v. 36 i. 11 p. 837 - 912
Evolutionary Systems: A Language Generating Device Inspired by Evolving Communities of Cells
by: Erzsébet Csuhaj-Varjú, Victor Mitrana v. 36 i. 11 p. 913 - 926
Class Hierarchy Specialization
by: Frank Tip, Peter F. Sweeney v. 36 i. 12 p. 927 - 982
Special Factors, Periodicity, and an Application to Sturmian Words
by: Arturo Carpi, Aldo de Luca v. 36 i. 12 p. 983 - 1006
Type Introduction for Equational Rewriting
by: Aart Middeldorp, Hitoshi Ohsaki v. 36 i. 12 p. 1007 - 1029
Semantics analysis through elementary meanings
by: Youichi Kobuchi, Takashi Saito, Hidenobu Nunome v. 37 i. 1 p. 1 - 19
Data structures for order-sensitive predicates in parallel nondeterministic systems
by: Desh Ranjan, Enrico Pontelli, Gopal Gupta v. 37 i. 1 p. 21 - 43
Accepting Zeno words: a way toward timed refinements
by: Béatrice Bérard, Claudine Picaronny v. 37 i. 1 p. 45 - 81
Computational complexity via programming languages: constant factors do matter
by: Amir M. Ben-Amram, Neil D. Jones v. 37 i. 2 p. 83 - 120
Efficiently building a parse tree from a regular expression
by: Danny Dubé, Marc Feeley v. 37 i. 2 p. 121 - 144
Some results on the Collatz problem
by: Stefan Andrei, Manfred Kudlek, Radu Stefan Niculescu v. 37 i. 2 p. 145 - 160
One-write algorithms for multivalued regular and atomic registers
by: Soma Chaudhuri, Martha J. Kosa, Jennifer L. Welch v. 37 i. 3 p. 161 - 192
The class Steiner minimal tree problem: a lower bound and test problem generation
by: Bo-Ting Yang, Paul Gillard v. 37 i. 3 p. 193 - 211
Fair sticker languages
by: Hendrik Jan Hoogeboom, Nike van Vugt v. 37 i. 3 p. 213 - 225

1999

Transformational Design of Real-Time Systems Part I: From Requirements to Program Specifications
by: Michael Schenke, Ernst-Rüdiger Olderog v. 36 i. 1 p. 1 - 65
Transformational Design of Real-Time Systems. Part II: From Program Specifications to Programs
by: Michael Schenke v. 36 i. 1 p. 67 - 96
Towards a Theory of Consistency Enforcement
by: Klaus-Dieter Schewe, Bernhard Thalheim v. 36 i. 2 p. 97 - 141
An Optimal Algorithm for Solving the Searchlight Guarding Problem on Weighted Two-Terminal Series-Parallel Graphs
by: William C. K. Yen, C. Y. Tang v. 36 i. 2 p. 143 - 172
Semantic Foundations of 4NF in Relational Database Design
by: Millist W. Vincent v. 36 i. 3 p. 173 - 213
Parallel PROFIT/COST Algorithms Through Fast Derandomization
by: Yijie Han, Yoshihide Igarashi v. 36 i. 3 p. 215 - 232
Comparing Expressibility of Normed BPA and Normed BPP Processes
by: Ivana Cerná, Mojmír Kretínský, Antonín Kucera v. 36 i. 3 p. 233 - 256
An Optimal Algorithm for Decomposing a Window into Maximal Quadtree Blocks
by: Guido Proietti v. 36 i. 4 p. 257 - 266
Reasoning with Examples: Propositional Formulae and Database Dependencies
by: Roni Khardon, Heikki Mannila, Dan Roth v. 36 i. 4 p. 267 - 286
On-Line Scheduling on a Single Machine: Minimizing the Total Completion Time
by: Amos Fiat, Gerhard J. Woeginger v. 36 i. 4 p. 287 - 293
Reasoning Algebraically about Loops
by: Ralph-Johan Back, Joakim von Wright v. 36 i. 4 p. 295 - 334
Causality for Debugging Mobile Agents
by: Pierpaolo Degano, Corrado Priami, Lone Leth, Bent Thomsen v. 36 i. 5 p. 335 - 374
Reasoning with First Order Nondeterministic Specifications
by: Beata Konikowska, Marcin Bialasik v. 36 i. 5 p. 375 - 403
Finding the k Most Vital Edges with Respect to Minimum Spanning Tree
by: Hong Shen v. 36 i. 5 p. 405 - 424
Optimal Bounds on the Gain of Permitting Dynamic Allocation of Communication Channels in Distributed Computing
by: Lars Lundberg, Håkan Lennerstad v. 36 i. 6 p. 425 - 446
Memory Requirements for Silent Stabilization
by: Shlomi Dolev, Mohamed G. Gouda, Marco Schneider v. 36 i. 6 p. 447 - 462
On the Cost-Effectiveness of PRAMs
by: Ferri Abolhassan, Jörg Keller, Wolfgang J. Paul v. 36 i. 6 p. 463 - 487
Two Graph Algorithms Derived
by: Jesús N. Ravelo v. 36 i. 6 p. 489 - 510

1998

Structured Numbers: Properties of a Hierarchy of Operations on Binary Trees
by: Vincent D. Blondel v. 35 i. 1 p. 1 - 15
Generating Words Lexicographically: An Average-Case Analysis
by: Rainer Kemp v. 35 i. 1 p. 17 - 89
Data Refinement of Mixed Specifications
by: Beverly A. Sanders v. 35 i. 2 p. 91 - 129
Refinement of Fair Action Systems
by: Ralph-Johan Back, Qiwen Xu v. 35 i. 2 p. 131 - 165
About the Collatz Conjecture
by: Stefan Andrei, Cristian Masalagiu v. 35 i. 2 p. 167 - 179
Conceptual Classes and System Classes in Object Databases
by: Elvira Locuratolo, Fausto Rabitti v. 35 i. 3 p. 181 - 210
Average-Case Complexity for the Execution of Recursive Definitions on Relational Databases
by: Wenceslas Fernandez de la Vega, Vangelis Th. Paschos, Andreas Stafylopatis v. 35 i. 3 p. 211 - 243
Context-Free Languages over Infinite Alphabets
by: Edward Y. C. Cheng, Michael Kaminski v. 35 i. 3 p. 245 - 267
Lattices in Machine Learning: Complexity Issues
by: Derrick G. Kourie, G. Deon Oosthuizen v. 35 i. 4 p. 269 - 292
Modularity and Expressibility for Nets of Relations
by: Alexander Moshe Rabinovich v. 35 i. 4 p. 293 - 327
On Time Computability of Functions in One-Way Cellular Automata
by: Thomas Buchholz, Martin Kutrib v. 35 i. 4 p. 329 - 352
A Fully Abstract Semantics for Causality in the \pi-Calculus
by: Michele Boreale, Davide Sangiorgi v. 35 i. 5 p. 353 - 400
DNA Computing, Sticker Systems, and Universality
by: Lila Kari, Gheorghe Paun, Grzegorz Rozenberg, Arto Salomaa, Sheng Yu v. 35 i. 5 p. 401 - 420
Partitioning a Sequence into Few Monotone Subsequences
by: Reuven Bar-Yehuda, Sergio Fogel v. 35 i. 5 p. 421 - 440
Consistent Records in Asynchronous Computations
by: Roberto Baldoni, Jean-Michel Hélary, Michel Raynal v. 35 i. 6 p. 441 - 455
A Logic-Based Approach to Program Flow Analysis
by: Shmuel Sagiv, Nissim Francez, Michael Rodeh, Reinhard Wilhelm v. 35 i. 6 p. 457 - 504
Nonfinite Axiomatizability of the Equational Theory of Shuffle
by: Zoltán Ésik, Michael Bertol v. 35 i. 6 p. 505 - 539
List Ranking on Meshes
by: Jop F. Sibeyn v. 35 i. 7 p. 543 - 566
Approximating Traces
by: Volker Diekert, Paul Gastin v. 35 i. 7 p. 567 - 593
On Finite Automata with Limited Nondeterminism
by: Hing Leung v. 35 i. 7 p. 595 - 624
Decision Problems Concerning Thinness and Slenderness of Formal Languages
by: Juha Honkala v. 35 i. 7 p. 625 - 636
Converting Untyped Formulas to Typed Ones
by: Jan Van den Bussche, Luca Cabibbo v. 35 i. 8 p. 637 - 643
Polytime Model Checking for Timed Probabilistic Computation Tree Logic
by: Danièle Beauquier, Anatol Slissenko v. 35 i. 8 p. 645 - 664
On a Relation Between Uniform Coding and Problems of the Form DTIMEF(F) =? DSPACEF(F)
by: Salvatore Caporaso, Michele Zito v. 35 i. 8 p. 665 - 672
Priority Conflict-Free Petri Nets
by: Hsu-Chun Yen v. 35 i. 8 p. 673 - 688
Bi-Catenation and Shuffle Product of Languages
by: Huei-Jan Shyr, Shyr-Shen Yu v. 35 i. 8 p. 689 - 707
d-Words and d-Languages
by: Chen-Ming Fan, Huei-Jan Shyr, Shyr-Shen Yu v. 35 i. 8 p. 709 - 727
Denotational Semantics of Object Specification
by: Amílcar Sernadas, Cristina Sernadas, Carlos Caleiro v. 35 i. 9 p. 729 - 773
A Tree-Based Mergesort
by: Alistair Moffat, Ola Petersson, Nicholas C. Wormald v. 35 i. 9 p. 775 - 793
Machine Scheduling with Availability Constraints
by: Eric Sanlaville, Günter Schmidt v. 35 i. 9 p. 795 - 811
M-Nets: An Algebra of High-Level Petri Nets, with an Application to the Semantics of Concurrent Programming Languages
by: Eike Best, Wojciech Fraczak, Richard P. Hopkins, Hanna Klaudel, Elisabeth Pelz v. 35 i. 10 p. 813 - 857
Amortized Constant Relaxed Rebalancing Using Standard Rotations
by: Kim S. Larsen v. 35 i. 10 p. 859 - 874
On Linear List Recursion in Parallel
by: Christoph Wedler, Christian Lengauer v. 35 i. 10 p. 875 - 909
Asymptotic Expansions of the Mergesort Recurrences
by: Hsien-Kuei Hwang v. 35 i. 11 p. 911 - 919
Fusion and Simultaneous Execution in the Refinement Calculus
by: Ralph-Johan Back, Michael J. Butler v. 35 i. 11 p. 921 - 949
Modular Correctness Proofs of Behavioural Implementations
by: Michel Bidoit, Rolf Hennicker v. 35 i. 11 p. 951 - 1005
Dijkstra-Scholten Predicate Calculus: Concepts and Misconceptions
by: Lex Bijlsma, Rob Nederpelt v. 35 i. 12 p. 1007 - 1036
A Transformation System for Concurrent Processes
by: Nicoletta De Francesco, Antonella Santone v. 35 i. 12 p. 1037 - 1073
Axioms for Generalized Graphs, Illustrated by a Cantor-Bernstein Proposition
by: Joost Engelfriet, Tjalling Gelsema v. 35 i. 12 p. 1075 - 1096

1997

Weakly Independent Database Schemes
by: Ke Wang, Weining Zhang, Siu-Cheung Chau v. 34 i. 1 p. 1 - 22
Net-Based Control Versus Rational Control. The Relation Between ITNC Vector Languages and Rational Relations
by: N. W. Keesmaat, H. C. M. Kleijn v. 34 i. 1 p. 23 - 57
Minimal Equational Representations of Recognizable Tree Languages
by: Zoltán Fülöp, Sándor Vágvölgyi v. 34 i. 1 p. 59 - 84
Decidability of Model Checking for Infinite-State Concurrent Systems
by: Javier Esparza v. 34 i. 2 p. 85 - 107
Distance Measures for Point Sets and their Computation
by: Thomas Eiter, Heikki Mannila v. 34 i. 2 p. 109 - 133
The Additivity Problem for Functional Dependencies in Incomplete Relations
by: Mark Levene, George Loizou v. 34 i. 2 p. 135 - 149
Computational Fractal Geometry with WFA
by: Karel Culik II, Jarkko Kari v. 34 i. 2 p. 151 - 166
Relational Database Constraints as Counterexamples
by: Levent V. Orman v. 34 i. 3 p. 167 - 189
Using Graph Coloring in an Algebraic Compiler
by: Teodor Rus, Sriram V. Pemmaraju v. 34 i. 3 p. 191 - 209
A Generalized Distribution Model for Random Recursive Trees
by: Alexander Shapiro v. 34 i. 3 p. 211 - 216
On the System of word equations x^i_1 x^i_2 ... x^i_m = y^i_1 y^i_2 ...y^i_n (i=1, 2, ...) in a Free Monoid
by: Ismo Hakala, Juha Kortelainen v. 34 i. 3 p. 217 - 230
Reduced Constants for Simple Cycle Graph Separation
by: Hristo Djidjev, Shankar M. Venkatesan v. 34 i. 3 p. 231 - 243
Efficient Algorithms for the Transformation Between Different Types of Binary Decision Diagrams
by: Petr Savický, Ingo Wegener v. 34 i. 4 p. 245 - 256
On the Interdependence Between Shuffle and Crossing-Over Operations
by: Victor Mitrana v. 34 i. 4 p. 257 - 266
Dynamic LL(k) Parsing
by: Arnd Rußmann v. 34 i. 4 p. 267 - 289
Locality Based Semantics for Process Algebras
by: Flavio Corradini, Rocco De Nicola v. 34 i. 4 p. 291 - 324
A Hierarchy of the Class of Apex NLC Graph Languages by Bounds on the Number of Nonterminal Nodes in Productions
by: Koichi Yamazaki v. 34 i. 5 p. 325 - 335
Minimum Feedback Vertex Sets in Comparability Graphs and Convex Bipartite Graphs
by: Y. Daniel Liang, Maw-Shang Chang v. 34 i. 5 p. 337 - 346
Implementing Daubechies Wavelet Transform with Weighted Finite Automata
by: Karel Culik II, Simant Dube v. 34 i. 5 p. 347 - 366
Fundamentals of Modelling Concurrency Using Discrete Relational Structures
by: Ryszard Janicki, Maciej Koutny v. 34 i. 5 p. 367 - 388
A Hierarchy of Uniquely Parsable Grammar Classes and Deterministic Acceptors
by: Kenichi Morita, Noritaka Nishihara, Yasunori Yamamoto, Zhiguo Zhang v. 34 i. 5 p. 389 - 410
Performance Analysis of Parallel Programs Based on Directed Acyclic Graphs
by: Georg Trogemann, Matthias Gente v. 34 i. 6 p. 411 - 428
An Optimal Emulator and VLSI Layout for Complete Binary Trees
by: Kemal Efe, Nancy Eleser v. 34 i. 6 p. 429 - 447
Algebraic Computational Models of OR-Parallel Execution of Prolog
by: Roberto Barbuti, Nicoletta De Francesco, Antonella Santone v. 34 i. 6 p. 449 - 489
A Survey of Stream Processing
by: Robert Stephens v. 34 i. 7 p. 491 - 541
On the Scalability and Mean-Time to Failure of k Resilient Protocols
by: Sampath Rangarajan, Yennun Huang, Satish K. Tripathi v. 34 i. 7 p. 543 - 556
Testing Bag-Containment of Conjunctive Queries
by: Nieves R. Brisaboa, Héctor J. Hernández v. 34 i. 7 p. 557 - 578
Minimal Communication Cost Software Construction in the Internet Environment
by: Chi-Chung Hui, Samuel T. Chanson v. 34 i. 8 p. 579 - 595
Code Generation Based on Formal BURS Therory and Heuristic Search
by: Albert Nymeyer, Joost-Pieter Katoen v. 34 i. 8 p. 597 - 635
A New Formula for Speedup and its Characterization
by: Janos Aczél, Wolfgang Ertel v. 34 i. 8 p. 637 - 652
A Fine-Grained Data-Flow Analysis Framework
by: C. Samuel Hsieh v. 34 i. 9 p. 653 - 665
Using the Causal Domain to Specify and verify Distributed Programs
by: Vijay K. Garg, Alexander I. Tomlinson v. 34 i. 9 p. 667 - 686
An Analysis and Implementation of an Efficient In-Place Bucket Sort
by: Apostolos Burnetas, Daniel Solow, Rishi Agarwal v. 34 i. 9 p. 687 - 700
Metric Semantics from Partial Order Semantics
by: Christel Baier, Mila E. Majster-Cederbaum v. 34 i. 9 p. 701 - 735
Prototyping Realistic Programming Languages Based on Formal Specifications
by: Arnd Poetzsch-Heffter v. 34 i. 10 p. 737 - 772
Context-Free Graph Grammars and Concatenation of Graphs
by: Joost Engelfriet, Jan Joris Vereijken v. 34 i. 10 p. 773 - 803
Performance Preorder and Competitive Equivalence
by: Flavio Corradini, Roberto Gorrieri, Marco Roccetti v. 34 i. 11 p. 805 - 835
Unconditional Transfer in Regulated Rewriting
by: Henning Fernau v. 34 i. 11 p. 837 - 857
Easy Sets and Hard Certificate Schemes
by: Lane A. Hemaspaandra, Jörg Rothe, Gerd Wechsung v. 34 i. 11 p. 859 - 879
Optimal Fault-Tolerant Computing on Multiprocessor Systems
by: John L. Bruno, Edward G. Coffman Jr. v. 34 i. 12 p. 881 - 904
The Use of Deleted Tuples in Database, Querying and Updating
by: Dominique Laurent, Viet Phan Luong, Nicolas Spyratos v. 34 i. 12 p. 905 - 925
Applications of a Categorical Framework for Conceptual Data Modelling
by: Arthur H. M. ter Hofstede, E. Lippe, Theo P. van der Weide v. 34 i. 12 p. 927 - 963

1996

Possibility and Impossibility Results in a Shared Memory Environment
by: Gadi Taubenfeld, Shlomo Moran v. 33 i. 1 p. 1 - 20
Kinded Type Inference for Parametric Overloading
by: Dominic Duggan, Gordon V. Cormack, John Ophel v. 33 i. 1 p. 21 - 68
A Theory of Bisimulation for the pi-Calculus
by: Davide Sangiorgi v. 33 i. 1 p. 69 - 97
Alias Analysis of Pointers in Pascal and Fortran 90: Dependence Analysis Between Pointer References
by: Aki Matsumoto, D. S. Han, Takao Tsuda v. 33 i. 2 p. 99 - 130
Multi-Granularity Locking for Nested Transactions: A Proof Using a Possibilities Mapping
by: John Lee, Alan Fekete v. 33 i. 2 p. 131 - 152
Parallel Composition of Assumption-Commitment Specifications: A Unifying Approach for Shared Variable and Distributed Message Passing Concurrency
by: Antonio Cau, Pierre Collette v. 33 i. 2 p. 153 - 176
Simple Extensions of 1-writer Atomic Variable Constructions to Multiwriter Ones
by: Sibsankar Haldar, K. Vidyasankar v. 33 i. 2 p. 177 - 202
Modeling Data-Intensive Reactive Systems with Relational Transition Systems
by: Alexander Tuzhilin, Zvi M. Kedem v. 33 i. 3 p. 203 - 231
Bounded Delay for a Free Address
by: Wim H. Hesselink v. 33 i. 3 p. 233 - 254
Optimizing the Costs of Hierarchical Quorum Consensus
by: Akhil Kumar, Kavindra Malik v. 33 i. 3 p. 255 - 275
Short Resolution Proofs for a Sequence of Tricky Formulas
by: Gunnar Stålmarck v. 33 i. 3 p. 277 - 280
On the Rational Subsets of the Free Group
by: Géraud Sénizergues v. 33 i. 3 p. 281 - 296
The Synthesis Problem of Petri Nets
by: Jörg Desel, Wolfgang Reisig v. 33 i. 4 p. 297 - 315
Timing and Causality in Process Algebra
by: Luca Aceto, David Murphy v. 33 i. 4 p. 317 - 350
The Log-Structured Merge-Tree (LSM-Tree)
by: Patrick E. O'Neil, Edward Cheng, Dieter Gawlick, Elizabeth J. O'Neil v. 33 i. 4 p. 351 - 385
Parallel Approximation Schemes for Problems on Planar Graphs
by: Josep Díaz, Maria J. Serna, Jacobo Torán v. 33 i. 4 p. 387 - 408
Forgetting Automata and Context-Free Languages
by: Petr Jancar, Frantisek Mráz, Martin Plátek v. 33 i. 5 p. 409 - 420
Algebraic Models of Microprocessors: Architecture and Organisation
by: Neal A. Harman, J. V. Tucker v. 33 i. 5 p. 421 - 456
Syntactic Complexity of Context-Free Grammars Over Word Monoids
by: Alexander Meduna v. 33 i. 5 p. 457 - 462
Undecidability of Restricted Uniform Recurrence Equations
by: Egon Wanke v. 33 i. 5 p. 463 - 475
Category-Based Modularisation for Equational Logic Programming
by: Razvan Diaconescu v. 33 i. 5 p. 477 - 510
Disambiguating Grammars by Exclusion of Sub-Parse Trees
by: Mikkel Thorup v. 33 i. 6 p. 511 - 522
A Kernel Language for Programmed Rewriting of (Hyper)graphs
by: Andrea Maggiolo-Schettini, Józef Winkowski v. 33 i. 6 p. 523 - 546
Chromatic Binary Search Trees. A Structure for Concurrent Rebalancing
by: Otto Nurmi, Eljas Soisalon-Soininen v. 33 i. 6 p. 547 - 557