Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Decidable fragments of simultaneous rigid reachability

Cortier, V., Ganzinger, H., Jacquemard, F., & Veanes, M. (1999). Decidable fragments of simultaneous rigid reachability. In J. Wiedermann, P. van Emde Boas, & M. Nielsen (Eds.), Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP-99) (pp. 250-260). Berlin, Germany: Springer.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3640-1 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3642-E
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Cortier, V.1, Autor           
Ganzinger, Harald1, Autor           
Jacquemard, Florent1, Autor           
Veanes, Margus1, Autor           
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: In this paper we prove decidability results of restricted fragments of simultaneous rigid reachability or SRR, that is the nonsymmetrical form of simultaneous rigid E-unification or SREU. The absence of symmetry enforces us to use different methods, than the ones that have been successful in the context of SREU (for example word equations). The methods that we use instead, involve finite (tree) automata techniques, and the decidability proofs provide precise computational complexity bounds. The main results are 1) monadic SRR with ground rule is PSPACE-complete, and 2) balanced SRR with ground rules is EXPTIME-complete. These upper bounds have been open already for corresponding fragments of SREU, for which only the hardness results have been known. The first result indicates the difference in computational power between fragments of SREU with ground rules and nonground rules, respectively, due to a straightforward encoding of word equations in monadic SREU (with nonground rules). The second result establishes the decidability and precise complexity of the largest known subfragment of nonmonadic SREU.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-121999
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 519691
Anderer: Local-ID: C1256104005ECAFC-858FA899FAA2C594C12567430056D5B4-Cortier-et-al-99
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Prague, Czech Republik
Start-/Enddatum: 1999

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP-99)
Genre der Quelle: Konferenzband
 Urheber:
Wiedermann, Jiri, Herausgeber
van Emde Boas, Peter, Herausgeber
Nielsen, Mogen, Herausgeber
Affiliations:
-
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 250 - 260 Identifikator: ISBN: 3-540-66224-3

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 1644 Artikelnummer: - Start- / Endseite: - Identifikator: -