4 Search Results for "Talcott, Carolyn L."

Document

DOI: 10.4230/LIPIcs.FSCD.2024.32

Termination of Generalized Term Rewriting Systems

Authors: Salvador Lucas

Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)

Abstract

We investigate termination of Generalized Term Rewriting Systems (GTRS), which extend Conditional Term Rewriting Systems by considering replacement restrictions on selected arguments of function symbols, as in Context-Sensitive Rewriting, and conditional rewriting rules whose conditional part may include not only a mix of the usual (reachability, joinability,...) conditions, but also atoms defined by a set of definite Horn clauses. GTRS can be used to prove confluence and termination of Generalized Rewrite Theories and Maude programs. We have characterized confluence of terminating GTRS as the joinability of a finite set of conditional pairs. Since termination of GTRS is underexplored to date, this paper introduces a Dependency Pair Framework which is well-suited to automatically (dis)prove termination of GTRS.

Cite as

Salvador Lucas. Termination of Generalized Term Rewriting Systems. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lucas:LIPIcs.FSCD.2024.32,
  author =	{Lucas, Salvador},
  title =	{{Termination of Generalized Term Rewriting Systems}},
  booktitle =	{9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)},
  pages =	{32:1--32:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-323-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{299},
  editor =	{Rehof, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.32},
  URN =		{urn:nbn:de:0030-drops-203616},
  doi =		{10.4230/LIPIcs.FSCD.2024.32},
  annote =	{Keywords: Program Analysis, Reduction-Based Systems, Termination}
}

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2024.143

Forcing, Transition Algebras, and Calculi

Authors: Go Hashimoto, Daniel Găină, and Ionuţ Ţuţu

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract

We bring forward a logical system of transition algebras that enhances many-sorted first-order logic using features from dynamic logics. The sentences we consider include compositions, unions, and transitive closures of transition relations, which are treated similarly to the actions used in dynamic logics in order to define necessity and possibility operators. This leads to a higher degree of expressivity than that of many-sorted first-order logic. For example, one can finitely axiomatize both the finiteness and the reachability of models, neither of which are ordinarily possible in many-sorted first-order logic. We introduce syntactic entailment and study basic properties such as compactness and completeness, showing that the latter does not hold when standard finitary proof rules are used. Consequently, we define proof rules having both finite and countably infinite premises, and we provide conditions under which completeness can be proved. To that end, we generalize the forcing method introduced in model theory by Robinson from a single signature to a category of signatures, and we apply it to obtain a completeness result for signatures that are at most countable.

Cite as

Go Hashimoto, Daniel Găină, and Ionuţ Ţuţu. Forcing, Transition Algebras, and Calculi. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 143:1-143:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hashimoto_et_al:LIPIcs.ICALP.2024.143,
  author =	{Hashimoto, Go and G\u{a}in\u{a}, Daniel and \c{T}u\c{t}u, Ionu\c{t}},
  title =	{{Forcing, Transition Algebras, and Calculi}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{143:1--143:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.143},
  URN =		{urn:nbn:de:0030-drops-202868},
  doi =		{10.4230/LIPIcs.ICALP.2024.143},
  annote =	{Keywords: Forcing, institution theory, calculi, algebraic specification, transition systems}
}

Document

DOI: 10.4230/DagRep.9.11.97

Composing Model-Based Analysis Tools (Dagstuhl Seminar 19481)

Authors: Francisco Durán, Robert Heinrich, Diego Pérez-Palacín, Carolyn L. Talcott, and Steffen Zschaler

Published in: Dagstuhl Reports, Volume 9, Issue 11 (2020)

Abstract

This report documents the program and the outcomes of the Dagstuhl Seminar 19481 "Composing Model-Based Analysis Tools". The key objective of the seminar was to provide more flexibility in model-driven engineering by bringing together representatives from industry and researchers in the formal methods and software engineering communities to establishing the foundations for a common understanding on the modularity and composition of modeling languages and model-based analyses.

Cite as

Francisco Durán, Robert Heinrich, Diego Pérez-Palacín, Carolyn L. Talcott, and Steffen Zschaler. Composing Model-Based Analysis Tools (Dagstuhl Seminar 19481). In Dagstuhl Reports, Volume 9, Issue 11, pp. 97-116, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Article{duran_et_al:DagRep.9.11.97,
  author =	{Dur\'{a}n, Francisco and Heinrich, Robert and P\'{e}rez-Palac{\'\i}n, Diego and Talcott, Carolyn L. and Zschaler, Steffen},
  title =	{{Composing Model-Based Analysis Tools (Dagstuhl Seminar 19481)}},
  pages =	{97--116},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2020},
  volume =	{9},
  number =	{11},
  editor =	{Dur\'{a}n, Francisco and Heinrich, Robert and P\'{e}rez-Palac{\'\i}n, Diego and Talcott, Carolyn L. and Zschaler, Steffen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.11.97},
  URN =		{urn:nbn:de:0030-drops-119853},
  doi =		{10.4230/DagRep.9.11.97},
  annote =	{Keywords: Modelling, Simulation, Semantics, Formal Methods, Software Engineering}
}

Document

DOI: 10.4230/DagSemProc.05081.7

Practical Techniques for Language Design and Prototyping

Authors: Mark-Oliver Stehr and Carolyn Talcott L.

Published in: Dagstuhl Seminar Proceedings, Volume 5081, Foundations of Global Computing (2006)

Abstract

Global computing involves the interplay of a vast variety of languages, but practially useful foundations for language specification and prototyping at the semantic level are lacking. In this talk we present a systematic approach consisting of three techniques: 1. A generic calculus of explicit substitutions with names (called CINNI) that allows us give a first-order representation of syntax to uniformly deal with all binding aspects. 2. An executable representation of Felleisen-style operational semantics in terms of first-order rewrite rules. 3. A logical framework, namely rewriting logic, that allows us to express (1) and (2) and, in addition, language aspects such as concurrency and non-determinism. We illustrate the use of these techniques in two applications: 1. A formal specification and analysis of PLAN, a Packet Language for Active Networks, that has been developed in the Switchware project at UPenn. This work was conducted in the scope of the DARPA Active Network Program. 2. The development of CIAO, a Calculus of Imperative Active Objects, a core language for concurrent object-oriented programming. It is especially designed to allow a the representation of practically relevant sublanguages of common object-oriented languages such as Java, C#, and C++. This second application is subject of ongoing work.

Cite as

Mark-Oliver Stehr and Carolyn Talcott L.. Practical Techniques for Language Design and Prototyping. In Foundations of Global Computing. Dagstuhl Seminar Proceedings, Volume 5081, pp. 1-38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{stehr_et_al:DagSemProc.05081.7,
  author =	{Stehr, Mark-Oliver and Talcott L., Carolyn},
  title =	{{Practical Techniques for Language Design and Prototyping}},
  booktitle =	{Foundations of Global Computing},
  pages =	{1--38},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5081},
  editor =	{Jos\'{e} Luiz Fiadeiro and Ugo Montanari and Martin Wirsing},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05081.7},
  URN =		{urn:nbn:de:0030-drops-3006},
  doi =		{10.4230/DagSemProc.05081.7},
  annote =	{Keywords: Rewriting logic, explicit substitutions, operational semantics, active networks, active objects}
}

Refine by Author
1 Durán, Francisco
1 Găină, Daniel
1 Hashimoto, Go
1 Heinrich, Robert
1 Lucas, Salvador
Show More...

Refine by Classification
2 Theory of computation → Equational logic and rewriting
2 Theory of computation → Logic and verification
1 General and reference → General literature
1 Theory of computation → Automated reasoning
1 Theory of computation → Proof theory

Refine by Keyword
1 Forcing
1 Formal Methods
1 Modelling
1 Program Analysis
1 Reduction-Based Systems
Show More...

Refine by Type
4 document

Refine by Publication Year
2 2024
1 2006
1 2020