de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Decidable fragments of simultaneous rigid reachability

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44263

Cortier,  Véronique
Programming Logics, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44474

Ganzinger,  Harald
Programming Logics, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44688

Jacquemard,  Florent
Programming Logics, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45662

Veanes,  Margus
Programming Logics, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

1999-2-004
(beliebiger Volltext), 11KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Cortier, V., Ganzinger, H., Jacquemard, F., & Veanes, M.(1999). Decidable fragments of simultaneous rigid reachability (MPI-I-1999-2-004). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-6F6E-6
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 forces us to use different methods, from the ones that have been successful in the context of SREU in the past (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 rules is PSPACE-complete, and 2) balanced SRR with ground rules is EXPTIME-complete. 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.