Werner Kuich
Proceedings of the 19th International Colloquium on Automata, Languages and Programming
ICALP, 1992.

@proceedings{ICALP-1992,
	address       = "Vienna, Austria",
	editor        = "Werner Kuich",
	isbn          = "3-540-55719-9",
	publisher     = "{Springer-Verlag}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 19th International Colloquium on Automata, Languages and Programming}",
	volume        = 623,
	year          = 1992,
}

Contents (58 items)

6 ×#algorithm
4 ×#complexity
4 ×#on the
3 ×#analysis
3 ×#graph
3 ×#petri net
3 ×#semantics
3 ×#testing
2 ×#approximate
2 ×#automaton

ICALP-1992-LiV #complexity

Philosophical Issues in Kolmogorov Complexity (ML, PMBV), pp. 1–15.

ICALP-1992-Straubing #complexity #first-order #power of

Circuit Complexity and the Expressive Power of Generalized First-Order Formulas (HS), pp. 16–27.

ICALP-1992-SantisPY #bound #proving #statistics #verification

One-Message Statistical Zero-Knowledge Proofs and Space-Bounded Verifier (ADS, GP, MY), pp. 28–40.

ICALP-1992-Keranen

Abelian Squares are Avoidable on 4 Letters (VK), pp. 41–52.

ICALP-1992-KarhumakiPR #context-free grammar #polynomial #testing

Polynomial Size Test Sets for Context-Free Languages (JK, WP, WR), pp. 53–64.

ICALP-1992-Nishida

Quasi-Deterministic 0L Systems (TYN), pp. 65–76.

ICALP-1992-BuntrockL #context-sensitive grammar #on the

On Growing Context-Sensitive Languages (GB, KL), pp. 77–88.

ICALP-1992-Shallit #linear #set

Numeration Systems, Linear Recurrences, and Regular Sets (JS), pp. 89–100.

ICALP-1992-Krob #decidability #multi #problem #similarity

The Equality Problem for Rational Series with Multiplicities in the Tropical Semiring is Undecidable (DK), pp. 101–112.

ICALP-1992-ClerboutRZ

Semi-Commutations and Rational Expressions (MC, YR, WZ), pp. 113–125.

ICALP-1992-IbarraT #automaton #finite

New Results Concerning Synchronized Finite Automata (OHI, NQT), pp. 126–137.

ICALP-1992-Engelfriet #graph grammar #normalisation

A Greibach Normal Form for Context-free Graph Grammars (JE), pp. 138–149.

ICALP-1992-PeladeauP #on the

On Reverse and General Definite Tree Languages (PP, AP), pp. 150–161.

ICALP-1992-ArvindHHKLMOSST #reduction #set

Reductions to Sets of Low Information Content (VA, YH, LAH, JK, AL, MM, MO, US, RS, TT), pp. 162–173.

ICALP-1992-SheuL

UP and the Low and High Hierarchies: A Relativized Separation (MJS, TJL), pp. 174–185.

ICALP-1992-Flajolet #algorithm #analysis

Analytic Analysis of Algorithms (PF), pp. 186–210.

ICALP-1992-KirschenhoferPS #analysis #how #probability #problem

How to Count Quickly and Accurately: A Unified Analysis of Probabilistic Counting and Other Related Problems (PK, HP, WS), pp. 211–222.

ICALP-1992-Schmid #algorithm #multi

The Average CRI-Length of a Tree Collision Resolution Algorithm in Presence of Multiplicity-Dependent Capture Effects (US), pp. 223–234.

ICALP-1992-DietzfelbingerGMP #polynomial #reliability

Polynomial Hash Functions Are Reliable (MD, JYG, YM, NP), pp. 235–246.

ICALP-1992-SekarRR #adaptation #pattern matching

Adaptive Pattern Matching (RCS, RR, IVR), pp. 247–260.

ICALP-1992-Mansour #approximate #random

Randomized Interpolation and Approximation of Sparse Polynomials (YM), pp. 261–272.

ICALP-1992-BodlaenderFW

Two Strikes Against Perfect Phylogeny (HLB, MRF, TW), pp. 273–283.

ICALP-1992-Zhang

Disjunctive Systems and L-Domains (GQZ), pp. 284–295.

ICALP-1992-ApostolicoBG #algorithm #parallel

Optimal Parallel Algorithms for Periods, Palindromes and Squares (AA, DB, ZG), pp. 296–307.

ICALP-1992-BroderFSU

Near-perfect Token Distribution (AZB, AMF, ES, EU), pp. 308–317.

ICALP-1992-Hagerup #integer #performance

Fast Integer Merging on the EREW PRAM (TH), pp. 318–329.

ICALP-1992-KhullerT #algorithm #approximate #graph

Approximation Algorithms for Graph Augmentation (SK, RT), pp. 330–341.

ICALP-1992-Westbrook #incremental #performance #testing

Fast Incremental Planarity Testing (JW), pp. 342–353.

ICALP-1992-Poutre #component #graph #maintenance

Maintenance of Triconnected Components of Graphs (JALP), pp. 354–365.

ICALP-1992-VaziraniY

Suboptimal Cuts: Their Enumeration, Weight and Number (VVV, MY), pp. 366–377.

ICALP-1992-Buchberger

Gröbner Bases: An Introduction (BB), pp. 378–379.

ICALP-1992-Bundgen #algorithm #perspective #term rewriting

Buchberger’s Algorithm: The Term Rewriter’s Point of View (RB), pp. 380–391.

ICALP-1992-Comon #constraints #term rewriting

Completion of Rewrite Systems with Membership Constraints (HC), pp. 392–403.

ICALP-1992-Rote #how #metric

A New Metric Between Polygons and How to Compute it (GR), pp. 404–415.

ICALP-1992-PatersonY #graph #nearest neighbour #on the

On Nearest-Neighbor Graphs (MP, FFY), pp. 416–426.

ICALP-1992-MatousekS #algorithm

A Tail Estimate for Mulmuley’s Segment Intersection Algorithm (JM, RS), pp. 427–438.

ICALP-1992-ChazelleR #bound #complexity #pointer

Lower Bounds on the Complexity of Simplex Range Reporting on a Pointer Machine (BC, BR), pp. 439–449.

ICALP-1992-KolaitisV #logic

Infinitary Logic for Computer Science (PGK, MYV), pp. 450–473.

ICALP-1992-ChangMP

Characterization of Temporal Property Classes (EYC, ZM, AP), pp. 474–486.

ICALP-1992-Ong #lazy evaluation #modelling #λ-calculus

Lazy λ Calculus: Theories, Models and Local Structure Characterization (CHLO), pp. 487–498.

ICALP-1992-LaenensVZ #logic programming #semantics

Logic Programming Semantics Made Easy (EL, DV, CZ), pp. 499–508.

ICALP-1992-Debray #analysis #complexity #data flow #logic programming #on the #source code

On the Complexity of Dataflow Analysis of Logic Programs (SKD), pp. 509–520.

ICALP-1992-CortesiFW #abstract interpretation #comparison

Comparison of Abstract Interpretations (AC, GF, WHW), pp. 521–532.

ICALP-1992-PhoaF #ml #semantics

A Proposed Categorial Semantics for Pure ML (WP, MPF), pp. 533–544.

ICALP-1992-HenzingerMP #question #what

What Good Are Digital Clocks? (TAH, ZM, AP), pp. 545–558.

ICALP-1992-MollerT #abstraction #behaviour

Behavioural Abstraction in TCCS (FM, CMNT), pp. 559–570.

ICALP-1992-BrownG #category theory #petri net

Timing Petri Nets Categorically (CB, DG), pp. 571–582.

ICALP-1992-GastinP #automaton #infinity

Asynchronous Cellular Automata for Infinite Traces (PG, AP), pp. 583–594.

ICALP-1992-HoogersKT #petri net #semantics

A Trace Semantics for Petri Nets (PWH, HCMK, PST), pp. 595–604.

ICALP-1992-Vogler #communication #petri net #refinement

Asynchronous Communication of Petri Nets and the Refinement of Transitions (WV), pp. 605–616.

ICALP-1992-MontanariY #approach #parametricity

A Parametric Approach to Localities (UM, DY), pp. 617–628.

ICALP-1992-DeganoP

Proved Trees (PD, CP), pp. 629–640.

ICALP-1992-Olderog #communication #interface

Interfaces between Languages for Communicating Systems (ERO), pp. 641–655.

ICALP-1992-SannellaT #algebra #development #source code #specification #towards

Towards Formal Development of Programs from Algebraic Specifications: Model-Theoretic Foundations (DS, AT), pp. 656–671.

ICALP-1992-FixFG #composition #unification

Program Composition via Unification (LF, NF, OG), pp. 672–684.

ICALP-1992-MilnerS #bisimulation

Barbed Bisimulation (RM, DS), pp. 685–695.

ICALP-1992-Rabinovich #concurrent #finite

Checking Equivalences Between Concurrent Systems of Finite Agents (AMR), pp. 696–707.

ICALP-1992-CleavelandSZ #probability #process #testing

Testing Preorders for Probabilistic Processes (RC, SAS, AEZ), pp. 708–719.