5 Search Results for "Talcott L., Carolyn"

Document
DOI: 10.4230/LIPIcs.MFCS.2025.14
Register Automata with Permutations

Authors: Mrudula Balachander, Emmanuel Filiot, Raffaella Gentilini, and Nikos Tzevelekos

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We propose Permutation Deterministic Register Automata (pDRAs), a deterministic register automaton model where we allow permutations of registers in transitions. The model enables minimal canonical representations and pDRAs can be tested for equivalence in polynomial time. The complexity of minimization is between GI (the complexity of graph isomorphism) and NP. We then introduce a subclass of pDRAs, called register automata with fixed permutation policy, where the register permutation discipline is stipulated globally. This class generalizes the model proposed by Benedikt, Ley and Puppis in 2010, and we show that it also admits minimal and canonical representations, based on a finite-index word equivalence relation. As an application, we show that for any regular data language L, the minimal register automaton with fixed permutation policy recognizing L can be actively learned in polynomial time using oracles for membership, equivalence and data-memorability queries. We show that all the oracles can be implemented in polynomial time, and so this yields a polynomial time minimization algorithm.
Cite as

Mrudula Balachander, Emmanuel Filiot, Raffaella Gentilini, and Nikos Tzevelekos. Register Automata with Permutations. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balachander_et_al:LIPIcs.MFCS.2025.14,
  author =	{Balachander, Mrudula and Filiot, Emmanuel and Gentilini, Raffaella and Tzevelekos, Nikos},
  title =	{{Register Automata with Permutations}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.14},
  URN =		{urn:nbn:de:0030-drops-241219},
  doi =		{10.4230/LIPIcs.MFCS.2025.14},
  annote =	{Keywords: Register automata, data words, equivalence, minimization, active learning}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.55
Model-Theoretic Forcing in Transition Algebra

Authors: Go Hashimoto and Daniel Găină

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We study Löwenheim-Skolem and Omitting Types theorems in Transition Algebra, a logical system obtained by enhancing many sorted first-order logic with features from dynamic logic. The sentences we consider include compositions, unions, and transitive closures of transition relations, which are treated similarly to actions in dynamic logics to define necessity and possibility operators. We show that Upward Löwenheim-Skolem theorem, any form of compactness, and joint Robinson consistency property fail due to the expressivity of transitive closures of transitions. In this non-compact many-sorted logical system, we develop a forcing technique method by generalizing the classical method of forcing used by Keisler to prove Omitting Types theorem. Instead of working within a single signature, we work with a directed diagram of signatures, which allows us to establish Downward Löwenheim-Skolem and Omitting Types theorems despite the fact that models interpret sorts as sets, possibly empty. Building on a complete system of proof rules for Transition Algebra, we extend it with additional proof rules to reason about constructor-based and/or finite transition algebras. We then establish the completeness of this extended system for a fragment of Transition Algebra obtained by restricting models to constructor-based and/or finite transition algebras.
Cite as

Go Hashimoto and Daniel Găină. Model-Theoretic Forcing in Transition Algebra. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hashimoto_et_al:LIPIcs.MFCS.2025.55,
  author =	{Hashimoto, Go and G\u{a}in\u{a}, Daniel},
  title =	{{Model-Theoretic Forcing in Transition Algebra}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{55:1--55:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.55},
  URN =		{urn:nbn:de:0030-drops-241629},
  doi =		{10.4230/LIPIcs.MFCS.2025.55},
  annote =	{Keywords: institutional model theory, algebraic specification, transition algebra, forcing, omitting types property, L\"{o}wenheim-Skolem properties, completeness}
}
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/LITES-v004-i001-a003
Quantitative Analysis of Consistency in NoSQL Key-Value Stores

Authors: Si Liu, Jatin Ganhotra, Muntasir Raihan Rahman, Son Nguyen, Indranil Gupta, and José Meseguer

Published in: LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1

Abstract
The promise of high scalability and availability has prompted many companies to replace traditional relational database management systems (RDBMS) with NoSQL key-value stores. This comes at the cost of relaxed consistency guarantees: key-value stores only guarantee eventual consistency in principle. In practice, however, many key-value stores seem to offer stronger consistency. Quantifying how well consistency properties are met is a non-trivial problem.  We address this problem by formally modeling key-value stores as probabilistic systems and quantitatively analyzing their consistency properties by both statistical model checking and implementation evaluation. We present for the first time a formal probabilistic model of Apache Cassandra, a popular NoSQL key-value store, and quantify how much Cassandra achieves various consistency guarantees under various conditions. To validate our model, we evaluate multiple consistency properties using two methods and compare them against each other. The two methods are: (1) an implementation-based evaluation of the source code; and (2) a statistical model checking analysis of our probabilistic model.
Cite as

Si Liu, Jatin Ganhotra, Muntasir Raihan Rahman, Son Nguyen, Indranil Gupta, and José Meseguer. Quantitative Analysis of Consistency in NoSQL Key-Value Stores. In LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1, pp. 03:1-03:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{liu_et_al:LITES-v004-i001-a003,
  author =	{Liu, Si and Ganhotra, Jatin and Rahman, Muntasir Raihan and Nguyen, Son and Gupta, Indranil and Meseguer, Jos\'{e}},
  title =	{{Quantitative Analysis of Consistency in NoSQL Key-Value Stores}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{03:1--03:26},
  ISSN =	{2199-2002},
  year =	{2017},
  volume =	{4},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v004-i001-a003},
  URN =		{urn:nbn:de:0030-drops-192649},
  doi =		{10.4230/LITES-v004-i001-a003},
  annote =	{Keywords: NoSQL Key-value Store, Consistency, Statistical Model Checking, Rewriting Logic, Maude}
}
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 Type
  • 5 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2020
  • 1 2017
  • 1 2006

  • Refine by Author
  • 1 Balachander, Mrudula
  • 1 Durán, Francisco
  • 1 Filiot, Emmanuel
  • 1 Ganhotra, Jatin
  • 1 Gentilini, Raffaella
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs
  • 1 LITES
  • 1 DagRep
  • 1 DagSemProc

  • Refine by Classification
  • 1 Computer systems organization → Cloud computing
  • 1 General and reference → General literature
  • 1 Information systems → Key-value stores
  • 1 Software and its engineering → Model checking
  • 1 Theory of computation → Formal languages and automata theory
  • Show More...

  • Refine by Keyword
  • 1 Consistency
  • 1 Formal Methods
  • 1 Löwenheim-Skolem properties
  • 1 Maude
  • 1 Modelling
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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