Kim Guldstrand Larsen, Sven Skyum, Glynn Winskel
Proceedings of the 25th International Colloquium on Automata, Languages and Programming
ICALP, 1998.

@proceedings{ICALP-1998,
	address       = "Aalborg, Denmark",
	editor        = "Kim Guldstrand Larsen and Sven Skyum and Glynn Winskel",
	isbn          = "3-540-64781-3",
	publisher     = "{Springer-Verlag}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 25th International Colloquium on Automata, Languages and Programming}",
	volume        = 1443,
	year          = 1998,
}

Contents (78 items)

8 ×#on the
6 ×#algorithm
6 ×#automaton
6 ×#performance
4 ×#complexity
4 ×#finite
4 ×#multi
3 ×#approach
3 ×#approximate
3 ×#calculus

ICALP-1998-KestenPR #algorithm #linear #logic #specification #verification

Algorithmic Verification of Linear Temporal Logic Specifications (YK, AP, LoR), pp. 1–16.

ICALP-1998-BorchertKS #first-order #on the

On Existentially First-Order Definable Languages and Their Relation to NP (BB, DK, FS), pp. 17–28.

ICALP-1998-RaymondTT #algebra #approach #communication #complexity

An Algebraic Approach to Communication Complexity (JFR, PT, DT), pp. 29–40.

ICALP-1998-AlurMP #partial order

Deciding Global Partial-Order Properties (RA, KLM, DP), pp. 41–52.

ICALP-1998-LiuS #algorithm #fixpoint #linear

Simple Linear-Time Algorithms for Minimal Fixed Points (XL, SAS), pp. 53–66.

ICALP-1998-HusfeldtR #problem

Hardness Results for Dynamic Problems by Extensions of Fredman and Saks’ Chronogram Method (TH, TR), pp. 67–78.

ICALP-1998-Hagerup #performance #ram

Simpler and Faster Dictionaries on the AC0 RAM (TH), pp. 79–90.

ICALP-1998-Lasota #similarity

Partial-Congruence Factorization of Bisimilarity Induced by Open Maps (SL), pp. 91–102.

ICALP-1998-DufourdFS #decidability

Reset Nets Between Decidability and Undecidability (CD, AF, PS), pp. 103–115.

ICALP-1998-Overmars #algorithm #geometry

Geometric Algorithms for Robotic Manipulation (MHO), pp. 116–117.

ICALP-1998-ChuangGHKL #canonical #encoding #graph #multi #order

Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses (RCNC, AG, XH, MYK, HIL), pp. 118–129.

ICALP-1998-GrafV #proving

Reducing Simple Polygons to Triangles — A Proof for an Improved Conjecture (TG, KV), pp. 130–139.

ICALP-1998-Walukiewicz #complexity

Difficult Configurations — On the Complexity of LTrL (IW), pp. 140–151.

ICALP-1998-BoigelotRW #automaton #integer #on the

On the Expressiveness of Real and Integer Arithmetic Automata (BB, SR, PW), pp. 152–163.

ICALP-1998-Peleg #distributed

Distributed Matroid Basis Completion via Elimination Upcast and Distributed Correction of Minimum-Weight Spanning Trees (DP), pp. 164–175.

ICALP-1998-Telle #constraints #independence #set

Independent Sets with Domination Constraints (MMH, JK, JAT), pp. 176–187.

ICALP-1998-MukundKRS #finite #protocol #robust

Robust Asynchronous Protocols Are Finite-State (MM, KNK, JR, MAS), pp. 188–199.

ICALP-1998-JancarKM #bisimulation #finite #process

Deciding Bisimulation-Like Equivalences with Finite-State Processes (PJ, AK, RM), pp. 200–211.

ICALP-1998-Wigderson #algorithm #probability #question

Do Probabilistic Algorithms Outperform Deterministic Ones? (AW), pp. 212–214.

ICALP-1998-Grolmusz

A Degree-Decreasing Lemma for (MOD q — MOD p) Circuits (VG), pp. 215–222.

ICALP-1998-Lu #combinator #generative #pseudo

Improved Pseudorandom Generators for Combinatorial Rectangles (CJL), pp. 223–234.

ICALP-1998-PnueliSS #validation

Translation Validation for Synchronous Languages (AP, OS, MS), pp. 235–246.

ICALP-1998-Zakharov #approach #decidability #equivalence #performance #source code

An Efficient and Unified Approach to the Decidability of Equivalence of Propositional Programs (VAZ), pp. 247–258.

ICALP-1998-JuknaZ #bound #branch #nondeterminism #on the #source code

On Branching Programs With Bounded Uncertainty (SJ, SZ), pp. 259–270.

ICALP-1998-Ben-AmramP #source code

CONS-Free Programs with Tree Input (AMBA, HP), pp. 271–282.

ICALP-1998-BaldanCM #graph #process

Concatenable Graph Processes: Relating Processes and Derivation Traces (PB, AC, UM), pp. 283–295.

ICALP-1998-GadducciM #axiom #process

Axioms for Contextual Net Processes (FG, UM), pp. 296–308.

ICALP-1998-Pitts #equivalence #logic

Existential Types: Logical Relations and Operational Equivalence (AMP), pp. 309–326.

ICALP-1998-MartinezR

Optimal Sampling Strategies in Quicksort (CM, SR), pp. 327–338.

ICALP-1998-DyerG #algorithm #polynomial

A Genuinely Polynomial-Time Algorithms for Sampling Two-Rowed Contingency Tables (MED, CSG), pp. 339–350.

ICALP-1998-PowerR #approach #composition #semantics

A Modular Approach to Denotational Semantics (JP, GR), pp. 351–362.

ICALP-1998-MalacariaH #game studies

Generalised Flowcharts and Games (PM, CH), pp. 363–374.

ICALP-1998-KaoW #fault #performance

Efficient Minimization of Numerical Summation Errors (MYK, JW), pp. 375–386.

ICALP-1998-BazganST #algorithm #approximate #performance #problem #similarity

Efficient Approximation Algorithms for the Subset-Sums Equality Problem (CB, MS, ZT), pp. 387–396.

ICALP-1998-Gimenez #recursion #type system

Structural Recursive Definitions in Type Theory (EG), pp. 397–408.

ICALP-1998-Lugiez #automaton #induction #proving #theorem proving

A Good Class of Tree Automata and Application to Inductive Theorem Proving (DL), pp. 409–420.

ICALP-1998-KarhumakiLP #behaviour #infinity #word

Locally Periodic Infinite Words and a Chaotic Behaviour (JK, AL, WP), pp. 421–430.

ICALP-1998-Pin

Bridges for Concatenation Hierarchies (JÉP), pp. 431–442.

ICALP-1998-Lin #proving #π-calculus

Complete Proof Systems for Observation Congruences in Finite-Control π-Calculus (HL), pp. 443–454.

ICALP-1998-VictorP #calculus #concurrent #constraints

Concurrent Constraints in the Fusion Calculus (BV, JP), pp. 455–469.

ICALP-1998-DamicoMM #automaton #on the

On Computing the Entropy of Cellular Automata (Md, GM, LM), pp. 470–481.

ICALP-1998-BuchsbaumGW #automaton #finite #on the

On the Determinization of Weighted Finite Automata (ALB, RG, JW), pp. 482–493.

ICALP-1998-Tiskin #matrix #parallel

Bulk-Synchronous Parallel Multiplication of Boolean Matrices (AT), pp. 494–506.

ICALP-1998-Touzet #term rewriting

A Complex Example of a Simplifying Rewrite System (HT), pp. 507–517.

ICALP-1998-Mellies #on the #theorem

On a Duality Between Kruskal and Dershowitz Theorems (PAM), pp. 518–529.

ICALP-1998-Walukiewicz98a #higher-order #reduction

A Total AC-Compatible Reduction Ordering on Higher-Order Terms (DW), pp. 530–542.

ICALP-1998-Henzinger #game studies #model checking #multi

Model Checking Game Properties of Multi-agent Systems (TAH), p. 543.

ICALP-1998-Gargano #network

Limited Wavelength Conversion in All-Optical Tree Networks (LG), pp. 544–555.

ICALP-1998-ChaudhuriSWZ #network

Computing Mimicking Networks (SC, KVS, FW, CDZ), pp. 556–567.

ICALP-1998-BaierKL #concurrent #metric #realtime #semantics

Metric Semantics for True Concurrent Real Time (CB, JPK, DL), pp. 568–579.

ICALP-1998-HenzingerRS #realtime

The Regular Real-Time Languages (TAH, JFR, PYS), pp. 580–591.

ICALP-1998-CiceroneSF

Static and Dynamic Low-Congested Interval Routing Schemes (SC, GDS, MF), pp. 592–603.

ICALP-1998-CookFMSS #network

Low-Bandwidth Routing and Electrical Power Networks (DC, VF, MVM, AS, YJS), pp. 604–615.

ICALP-1998-HengleinR #automaton #complexity #constraints #recursion #type system

Constraint Automata and the Complexity of Recursive Subtype Entailment (FH, JR), pp. 616–627.

ICALP-1998-Vardi #automaton #reasoning

Reasoning about The Past with Two-Way Automata (MYV), pp. 628–641.

ICALP-1998-Valiant #architecture

A Neuroidal Architecture for Cognitive Computation (LGV), pp. 642–669.

ICALP-1998-PelegR #approximate #communication

Deterministic Polylog Approximation for Minimum Communication Spanning Trees (DP, ER), pp. 670–681.

ICALP-1998-CzumajL #approximate #polynomial

A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity (AC, AL), pp. 682–694.

ICALP-1998-Sewell #distributed #type system #π-calculus

Global/Local Subtyping and Capability Inference for a Distributed π-calculus (PS), pp. 695–706.

ICALP-1998-LiC #bisimulation #congruence #π-calculus

Checking Strong/Weak Bisimulation Equivalences and Observation Congruence for the π-Calculus (ZL, HC), pp. 707–718.

ICALP-1998-BiniCMM #matrix

Inversion of Circulant Matrices over Zm (DB, GMDC, GM, LM), pp. 719–730.

ICALP-1998-PlandowskiR #encoding #equation #word

Application of Lempel-Ziv Encodings to the Solution of Words Equations (WP, WR), pp. 731–742.

ICALP-1998-GhaniPR

Explicit Substitutions for Constructive Necessity (NG, VdP, ER), pp. 743–754.

ICALP-1998-Barthe

The Relevance of Proof-Irrelevance (GB), pp. 755–768.

ICALP-1998-Brassard #information management #quantum

New Horizons in Quantum Information Processing (GB), pp. 769–771.

ICALP-1998-DamgardP #interactive #performance

Sequential Iteration of Interactive Arguments and an Efficient Zero-Knowledge Argument for NP (ID, BP), pp. 772–783.

ICALP-1998-SantisCPY #image

Image Density is Complete for Non-Interactive-SZK (ADS, GDC, GP, MY), pp. 784–795.

ICALP-1998-HertlingW

Randomness Spaces (PH, KW), pp. 796–807.

ICALP-1998-BucciarelliS

Totality, Definability and Boolean Ciruits (AB, IS), pp. 808–819.

ICALP-1998-BrassardHT #quantum

Quantum Counting (GB, PH, AT), pp. 820–831.

ICALP-1998-AkutsuY #biology #complexity #on the #problem

On the Complexity of Deriving Score Functions from Examples for Problems in Molecular Biology (TA, MY), pp. 832–843.

ICALP-1998-FournetG #calculus

A Hierarchy of Equivalences for Asynchronous Calculi (CF, GG), pp. 844–855.

ICALP-1998-MerroS #calculus #on the

On Asynchrony in Name-Passing Calculi (MM, DS), pp. 856–867.

ICALP-1998-Abadi

Protection in Programming-Language Translations (MA), pp. 868–883.

ICALP-1998-PetersenR #performance #queue #simulation

Efficient Simulations by Queue Machines (HP, JMR), pp. 884–895.

ICALP-1998-DurisJKL #finite #multi #power of

Power of Cooperation and Multihead Finite Systems (PD, TJ, MK, KL), pp. 896–907.

ICALP-1998-Danvy

A Simple Solution to Type Specialization (OD), pp. 908–917.

ICALP-1998-TahaBS #axiom #multi #programming #type safety

Multi-Stage Programming: Axiomatization and Type Safety (WT, ZEAB, TS), pp. 918–929.