Number of the records: 1
Ground reachability and joinability in linear term rewriting systems are fixed parameter tractable with respect to depth
- 1.
SYSNO ASEP 0476164 Document Type C - Proceedings Paper (int. conf.) R&D Document Type Conference Paper Title Ground reachability and joinability in linear term rewriting systems are fixed parameter tractable with respect to depth Author(s) de Oliveira Oliveira, Mateus (MU-W) RID, SAI, ORCID Article number 25 Source Title 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). - Dagstuhl : Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2017 / Guo J. ; Hermelin D. - ISSN 1868-8969 - ISBN 978-3-95977-023-1 Pages s. 1-12 Number of pages 12 s. Publication form Online - E Action 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) Event date 24.08.2016 - 26.08.2016 VEvent location Aarhus Country DK - Denmark Event type WRD Language eng - English Country DE - Germany Keywords linear term rewriting systems ; ground reachability ; ground joinability ; fixed parameter tractability Subject RIV BA - General Mathematics OECD category Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) Institutional support MU-W - RVO:67985840 EID SCOPUS 85014629211 DOI 10.4230/LIPIcs.IPEC.2016.25 Annotation The ground term reachability problem consists in determining whether a given variable-free term t can be transformed into a given variable-free term t' by the application of rules from a term rewriting system R. The joinability problem, on the other hand, consists in determining whether there exists a variable-free term t'' which is reachable both from t and from t'. Both problems have proven to be of fundamental importance for several subfields of computer science. Nevertheless, these problems are undecidable even when restricted to linear term rewriting systems. In this work, we approach reachability and joinability in linear term rewriting systems from the perspective of parameterized complexity theory, and show that these problems are fixed parameter tractable with respect to the depth of derivations. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2018
Number of the records: 1