Search Results

Documents authored by Panangaden, Prakash

Document
DOI: 10.4230/LIPIcs.CALCO.2021.7
Tensor of Quantitative Equational Theories

Authors: Giorgio Bacci, Radu Mardare, Prakash Panangaden, and Gordon Plotkin

Published in: LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)

Abstract
We develop a theory for the commutative combination of quantitative effects, their tensor, given as a combination of quantitative equational theories that imposes mutual commutation of the operations from each theory. As such, it extends the sum of two theories, which is just their unrestrained combination. Tensors of theories arise in several contexts; in particular, in the semantics of programming languages, the monad transformer for global state is given by a tensor. We show that under certain assumptions on the quantitative theories the free monad that arises from the tensor of two theories is the categorical tensor of the free monads on the theories. As an application, we provide the first algebraic axiomatizations of labelled Markov processes and Markov decision processes. Apart from the intrinsic interest in the axiomatizations, it is pleasing they are obtained compositionally by means of the sum and tensor of simpler quantitative equational theories.
Cite as

Giorgio Bacci, Radu Mardare, Prakash Panangaden, and Gordon Plotkin. Tensor of Quantitative Equational Theories. In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bacci_et_al:LIPIcs.CALCO.2021.7,
  author =	{Bacci, Giorgio and Mardare, Radu and Panangaden, Prakash and Plotkin, Gordon},
  title =	{{Tensor of Quantitative Equational Theories}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.7},
  URN =		{urn:nbn:de:0030-drops-153628},
  doi =		{10.4230/LIPIcs.CALCO.2021.7},
  annote =	{Keywords: Quantitative equational theories, Tensor, Monads, Quantitative Effects}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2021.118
Optimal Spectral-Norm Approximate Minimization of Weighted Finite Automata

Authors: Borja Balle, Clara Lacroce, Prakash Panangaden, Doina Precup, and Guillaume Rabusseau

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We address the approximate minimization problem for weighted finite automata (WFAs) with weights in ℝ, over a one-letter alphabet: to compute the best possible approximation of a WFA given a bound on the number of states. This work is grounded in Adamyan-Arov-Krein approximation theory, a remarkable collection of results on the approximation of Hankel operators. In addition to its intrinsic mathematical relevance, this theory has proven to be very effective for model reduction. We adapt these results to the framework of weighted automata over a one-letter alphabet. We provide theoretical guarantees and bounds on the quality of the approximation in the spectral and 𝓁² norm. We develop an algorithm that, based on the properties of Hankel operators, returns the optimal approximation in the spectral norm.
Cite as

Borja Balle, Clara Lacroce, Prakash Panangaden, Doina Precup, and Guillaume Rabusseau. Optimal Spectral-Norm Approximate Minimization of Weighted Finite Automata. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 118:1-118:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{balle_et_al:LIPIcs.ICALP.2021.118,
  author =	{Balle, Borja and Lacroce, Clara and Panangaden, Prakash and Precup, Doina and Rabusseau, Guillaume},
  title =	{{Optimal Spectral-Norm Approximate Minimization of Weighted Finite Automata}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{118:1--118:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.118},
  URN =		{urn:nbn:de:0030-drops-141873},
  doi =		{10.4230/LIPIcs.ICALP.2021.118},
  annote =	{Keywords: Weighted finite automata, approximate minimization, Hankel matrices, AAK Theory}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.103
Bisimulation Metrics for Weighted Automata

Authors: Borja Balle, Pascale Gourdeau, and Prakash Panangaden

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We develop a new bisimulation (pseudo)metric for weighted finite automata (WFA) that generalizes Boreale's linear bisimulation relation. Our metrics are induced by seminorms on the state space of WFA. Our development is based on spectral properties of sets of linear operators. In particular, the joint spectral radius of the transition matrices of WFA plays a central role. We also study continuity properties of the bisimulation pseudometric, establish an undecidability result for computing the metric, and give a preliminary account of applications to spectral learning of weighted automata.
Cite as

Borja Balle, Pascale Gourdeau, and Prakash Panangaden. Bisimulation Metrics for Weighted Automata. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 103:1-103:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{balle_et_al:LIPIcs.ICALP.2017.103,
  author =	{Balle, Borja and Gourdeau, Pascale and Panangaden, Prakash},
  title =	{{Bisimulation Metrics for Weighted Automata}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{103:1--103:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.103},
  URN =		{urn:nbn:de:0030-drops-73959},
  doi =		{10.4230/LIPIcs.ICALP.2017.103},
  annote =	{Keywords: weighted automata, bisimulation, metrics, spectral theory, learning}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.105
Expressiveness of Probabilistic Modal Logics, Revisited

Authors: Nathanaël Fijalkow, Bartek Klin, and Prakash Panangaden

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
Labelled Markov processes are probabilistic versions of labelled transition systems. In general, the state space of a labelled Markov process may be a continuum. Logical characterizations of probabilistic bisimulation and simulation were given by Desharnais et al. These results hold for systems defined on analytic state spaces and assume that there are countably many labels in the case of bisimulation and finitely many labels in the case of simulation. In this paper, we first revisit these results by giving simpler and more streamlined proofs. In particular, our proof for simulation has the same structure as the one for bisimulation, relying on a new result of a topological nature. This departs from the known proof for this result, which uses domain theory techniques and falls out of a theory of approximation of Labelled Markov processes. Both our proofs assume the presence of countably many labels. We investigate the necessity of this assumption, and show that the logical characterization of bisimulation may fail when there are uncountably many labels. However, with a stronger assumption on the transition functions (continuity instead of just measurability), we can regain the logical characterization result, for arbitrarily many labels. These new results arose from a new game-theoretic way of understanding probabilistic simulation and bisimulation.
Cite as

Nathanaël Fijalkow, Bartek Klin, and Prakash Panangaden. Expressiveness of Probabilistic Modal Logics, Revisited. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 105:1-105:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{fijalkow_et_al:LIPIcs.ICALP.2017.105,
  author =	{Fijalkow, Nathana\"{e}l and Klin, Bartek and Panangaden, Prakash},
  title =	{{Expressiveness of Probabilistic Modal Logics, Revisited}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{105:1--105:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.105},
  URN =		{urn:nbn:de:0030-drops-73683},
  doi =		{10.4230/LIPIcs.ICALP.2017.105},
  annote =	{Keywords: probabilistic modal logic, probabilistic bisimulation, probabilistic simulation}
}
Document
DOI: 10.4230/DagSemProc.06341.1
06341 Abstracts Collection – Computational Structures for Modelling Space, Time and Causality

Authors: Ralph Kopperman, Prakash Panangaden, Michael B. Smyth, and Dieter Spreen

Published in: Dagstuhl Seminar Proceedings, Volume 6341, Computational Structures for Modelling Space, Time and Causality (2007)

Abstract
From 20.08.06 to 25.08.06, the Dagstuhl Seminar 06341 ``Computational Structures for Modelling Space, Time and Causality'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Ralph Kopperman, Prakash Panangaden, Michael B. Smyth, and Dieter Spreen. 06341 Abstracts Collection – Computational Structures for Modelling Space, Time and Causality. In Computational Structures for Modelling Space, Time and Causality. Dagstuhl Seminar Proceedings, Volume 6341, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{kopperman_et_al:DagSemProc.06341.1,
  author =	{Kopperman, Ralph and Panangaden, Prakash and Smyth, Michael B. and Spreen, Dieter},
  title =	{{06341 Abstracts Collection – Computational Structures for Modelling Space, Time and Causality}},
  booktitle =	{Computational Structures for Modelling Space, Time and Causality},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6341},
  editor =	{Ralph Kopperman and Prakash Panangaden and Michael B. Smyth and Dieter Spreen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06341.1},
  URN =		{urn:nbn:de:0030-drops-9000},
  doi =		{10.4230/DagSemProc.06341.1},
  annote =	{Keywords: Borel hierarchy, causets, Chu spaces, computations in higher types, computable analysis, constructive topology, differential calculus, digital topology, dihomotopy, domain theory, domain representation, formal topology, higher dimensional automata, mereo\backslash-topology, partial metrics}
}
Document
DOI: 10.4230/DagSemProc.04351.1
04351 Abstracts Collection – Spatial Representation: Discrete vs. Continuous Computational Models

Authors: Ralph Kopperman, Prakash Panangaden, Michael B. Smyth, Dieter Spreen, and Julian Webster

Published in: Dagstuhl Seminar Proceedings, Volume 4351, Spatial Representation: Discrete vs. Continuous Computational Models (2005)

Abstract
From 22.08.04 to 27.08.04, the Dagstuhl Seminar 04351 ``Spatial Representation: Discrete vs. Continuous Computational Models'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Ralph Kopperman, Prakash Panangaden, Michael B. Smyth, Dieter Spreen, and Julian Webster. 04351 Abstracts Collection – Spatial Representation: Discrete vs. Continuous Computational Models. In Spatial Representation: Discrete vs. Continuous Computational Models. Dagstuhl Seminar Proceedings, Volume 4351, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{kopperman_et_al:DagSemProc.04351.1,
  author =	{Kopperman, Ralph and Panangaden, Prakash and Smyth, Michael B. and Spreen, Dieter and Webster, Julian},
  title =	{{04351 Abstracts Collection – Spatial Representation: Discrete vs. Continuous Computational Models}},
  booktitle =	{Spatial Representation: Discrete vs. Continuous Computational Models},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4351},
  editor =	{Ralph Kopperman and Michael B. Smyth and Dieter Spreen and Julian Webster},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04351.1},
  URN =		{urn:nbn:de:0030-drops-1742},
  doi =		{10.4230/DagSemProc.04351.1},
  annote =	{Keywords: Domain theory , formal topology , constructive topology , domain representation, space-time , quantum gravity , inverse limit construction, matroid geometry , descriptive set theory , Borel hierarchy , Hausdorff difference hierarchy , Wadge degree partial metric , fractafold , region geometry , oriented projective geometry}
}
Document
DOI: 10.4230/DagSemProc.04351.5
A domain of spacetime intervals in general relativity

Authors: Keye Martin and Prakash Panangaden

Published in: Dagstuhl Seminar Proceedings, Volume 4351, Spatial Representation: Discrete vs. Continuous Computational Models (2005)

Abstract
We prove that a globally hyperbolic spacetime with its causality relation is a bicontinuous poset whose interval topology is the manifold topology. This implies that from only a countable dense set of events and the causality relation, it is possible to reconstruct a globally hyperbolic spacetime in a purely order theoretic manner. The ultimate reason for this is that globally hyperbolic spacetimes belong to a category that is equivalent to a special category of domains called interval domains. We obtain a mathematical setting in which one can study causality independently of geometry and differentiable structure, and which also suggests that spacetime emanates from something discrete.
Cite as

Keye Martin and Prakash Panangaden. A domain of spacetime intervals in general relativity. In Spatial Representation: Discrete vs. Continuous Computational Models. Dagstuhl Seminar Proceedings, Volume 4351, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{martin_et_al:DagSemProc.04351.5,
  author =	{Martin, Keye and Panangaden, Prakash},
  title =	{{A domain of spacetime intervals in general relativity}},
  booktitle =	{Spatial Representation: Discrete vs. Continuous Computational Models},
  pages =	{1--28},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4351},
  editor =	{Ralph Kopperman and Michael B. Smyth and Dieter Spreen and Julian Webster},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04351.5},
  URN =		{urn:nbn:de:0030-drops-1350},
  doi =		{10.4230/DagSemProc.04351.5},
  annote =	{Keywords: Causality , spacetime , global hyperbolicity , interval domains , bicontinuous posets , spacetime topology}
}
Document
DOI: 10.4230/DagSemProc.04351.2
04351 Summary – Spatial Representation: Discrete vs. Continuous Computational Models

Authors: Ralph Kopperman, Prakash Panangaden, Michael B. Smyth, Dieter Spreen, and Julian Webster

Published in: Dagstuhl Seminar Proceedings, Volume 4351, Spatial Representation: Discrete vs. Continuous Computational Models (2005)

Abstract
Topological notions and methods are used in various areas of the physical sciences and engineering, and therefore computer processing of topological data is important. Separate from this, but closely related, are computer science uses of topology: applications to programming language semantics and computing with exact real numbers are important examples. The seminar concentrated on an important approach, which is basic to all these applications, i.e. spatial representation.
Cite as

Ralph Kopperman, Prakash Panangaden, Michael B. Smyth, Dieter Spreen, and Julian Webster. 04351 Summary – Spatial Representation: Discrete vs. Continuous Computational Models. In Spatial Representation: Discrete vs. Continuous Computational Models. Dagstuhl Seminar Proceedings, Volume 4351, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{kopperman_et_al:DagSemProc.04351.2,
  author =	{Kopperman, Ralph and Panangaden, Prakash and Smyth, Michael B. and Spreen, Dieter and Webster, Julian},
  title =	{{04351 Summary – Spatial Representation: Discrete vs. Continuous Computational Models}},
  booktitle =	{Spatial Representation: Discrete vs. Continuous Computational Models},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4351},
  editor =	{Ralph Kopperman and Michael B. Smyth and Dieter Spreen and Julian Webster},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04351.2},
  URN =		{urn:nbn:de:0030-drops-1710},
  doi =		{10.4230/DagSemProc.04351.2},
  annote =	{Keywords: Domain theory , formal topology , constructive topology , domain representation , space-time , quantum gravity , inverse limit construction , matroid geometry , descriptive set theory , Borel hierarchy , Hausdorff difference hierarchy , Wadge degree , partial metric , fractafold , region geometry}
}
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