English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  An implementation of the Hopcroft and Tarjan planarity test and embedding algorithm

Mehlhorn, K., Mutzel, P., & Näher, S.(1993). An implementation of the Hopcroft and Tarjan planarity test and embedding algorithm (MPI-I-93-151). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

Files

show Files
hide Files
:
MPI-I-93-151.pdf (Any fulltext), 373KB
Name:
MPI-I-93-151.pdf
Description:
-
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Mehlhorn, Kurt1, Author           
Mutzel, Petra1, Author           
Näher, Stefan1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: We design new inference systems for total orderings by applying rewrite techniques to chaining calculi. Equality relations may either be specified axiomatically or built into the deductive calculus via paramodulation or superposition. We demonstrate that our inference systems are compatible with a concept of (global) redundancy for clauses and inferences that covers such widely used simplification techniques as tautology deletion, subsumption, and demodulation. A key to the practicality of chaining techniques is the extent to which so-called variable chainings can be restricted. Syntactic ordering restrictions on terms and the rewrite techniques which account for their completeness considerably restrict variable chaining. We show that variable elimination is an admissible simplification techniques within our redundancy framework, and that consequently for dense total orderings without endpoints no variable chaining is needed at all.

Details

show
hide
Language(s): eng - English
 Dates: 1993
 Publication Status: Issued
 Pages: 20 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: URI: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/93-151
Report Nr.: MPI-I-93-151
BibTex Citekey: Mehlhorn93
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -