2 Search Results for "Sternagel, Thomas"

Document
DOI: 10.4230/LIPIcs.FSCD.2016.29
Certifying Confluence of Almost Orthogonal CTRSs via Exact Tree Automata Completion

Authors: Christian Sternagel and Thomas Sternagel

Published in: LIPIcs, Volume 52, 1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016)

Abstract
Suzuki et al. showed that properly oriented, right-stable, orthogonal, and oriented conditional term rewrite systems with extra variables in right-hand sides are confluent. We present our Isabelle/HOL formalization of this result, including two generalizations. On the one hand, we relax proper orientedness and orthogonality to extended proper orientedness and almost orthogonality modulo infeasibility, as suggested by Suzuki et al. On the other hand, we further loosen the requirements of the latter, enabling more powerful methods for proving infeasibility of conditional critical pairs. Furthermore, we formalized a construction by Jacquemard that employs exact tree automata completion for non-reachability analysis and apply it to certify infeasibility of conditional critical pairs. Combining these two results and extending the conditional confluence checker ConCon accordingly, we are able to automatically prove and certify confluence of an important class of conditional term rewrite systems.
Cite as

Christian Sternagel and Thomas Sternagel. Certifying Confluence of Almost Orthogonal CTRSs via Exact Tree Automata Completion. In 1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 52, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{sternagel_et_al:LIPIcs.FSCD.2016.29,
  author =	{Sternagel, Christian and Sternagel, Thomas},
  title =	{{Certifying Confluence of Almost Orthogonal CTRSs via Exact Tree Automata Completion}},
  booktitle =	{1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-010-1},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{52},
  editor =	{Kesner, Delia and Pientka, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2016.29},
  URN =		{urn:nbn:de:0030-drops-59996},
  doi =		{10.4230/LIPIcs.FSCD.2016.29},
  annote =	{Keywords: certification, conditional term rewriting, confluence, infeasible critical pairs, non-reachability}
}
Document
DOI: 10.4230/LIPIcs.RTA.2015.223
Conditional Complexity

Authors: Cynthia Kop, Aart Middeldorp, and Thomas Sternagel

Published in: LIPIcs, Volume 36, 26th International Conference on Rewriting Techniques and Applications (RTA 2015)

Abstract
We propose a notion of complexity for oriented conditional term rewrite systems. This notion is realistic in the sense that it measures not only successful computations but also partial computations that result in a failed rule application. A transformation to unconditional context-sensitive rewrite systems is presented which reflects this complexity notion, as well as a technique to derive runtime and derivational complexity bounds for the latter.
Cite as

Cynthia Kop, Aart Middeldorp, and Thomas Sternagel. Conditional Complexity. In 26th International Conference on Rewriting Techniques and Applications (RTA 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 36, pp. 223-240, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kop_et_al:LIPIcs.RTA.2015.223,
  author =	{Kop, Cynthia and Middeldorp, Aart and Sternagel, Thomas},
  title =	{{Conditional Complexity}},
  booktitle =	{26th International Conference on Rewriting Techniques and Applications (RTA 2015)},
  pages =	{223--240},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-85-9},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{36},
  editor =	{Fern\'{a}ndez, Maribel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2015.223},
  URN =		{urn:nbn:de:0030-drops-51999},
  doi =		{10.4230/LIPIcs.RTA.2015.223},
  annote =	{Keywords: conditional term rewriting, complexity}
}
  • Refine by Author
  • 2 Sternagel, Thomas
  • 1 Kop, Cynthia
  • 1 Middeldorp, Aart
  • 1 Sternagel, Christian

  • Refine by Classification

  • Refine by Keyword
  • 2 conditional term rewriting
  • 1 certification
  • 1 complexity
  • 1 confluence
  • 1 infeasible critical pairs
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2015
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact