English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Relating Semantic and Proof-Theoretic Concepts for Polynomial Time Decidability of Uniform Word Problems

Ganzinger, H. (2001). Relating Semantic and Proof-Theoretic Concepts for Polynomial Time Decidability of Uniform Word Problems. In D. A. Williams (Ed.), Proceedings of the 16th IEEE Symposium on Logic in Computer Science (LICS-01) (pp. 81-90). Los Alamitos, USA: IEEE.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3235-E Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3237-A
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Ganzinger, Harald1, Author           
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Content

show
hide
Free keywords: -
 Abstract: In this paper we compare three approaches to polynomial time decidability for uniform word problems for quasi-varieties. Two of the approaches, by Evans and Burris, respectively, are semantical, referring to certain embeddability and axiomatizability properties. The third approach is proof-theoretic in nature, inspired by McAllester's concept of local inference. We define two closely related notions of locality for equational Horn theories and show that both the criteria by Evans and Burris lie in between these two concepts. In particular, our notion of weak locality subsumes both Evans' and Burris' method.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-122001
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 519832
Other: Local-ID: C1256104005ECAFC-271953657FA398B3C1256AB50054F798-Ganzinger-01-lics
 Degree: -

Event

show
hide
Title: LICS 2001
Place of Event: Boston, USA
Start-/End Date: 2001-06-16 - 2001-06-19

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the 16th IEEE Symposium on Logic in Computer Science (LICS-01)
Source Genre: Proceedings
 Creator(s):
Williams, Denise A., Editor
Affiliations:
-
Publ. Info: Los Alamitos, USA : IEEE
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 81 - 90 Identifier: ISBN: 0-7695-1281-x