18 Search Results for "Taylor, Peter"


Document
On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras

Authors: Peter Mayr

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)


Abstract
For a fixed finite algebra 𝐀, we consider the decision problem SysTerm(𝐀): does a given system of term equations have a solution in 𝐀? This is equivalent to a constraint satisfaction problem (CSP) for a relational structure whose relations are the graphs of the basic operations of 𝐀. From the complexity dichotomy for CSP over fixed finite templates due to Bulatov [Bulatov, 2017] and Zhuk [Zhuk, 2017], it follows that SysTerm(𝐀) for a finite algebra 𝐀 is in P if 𝐀 has a not necessarily idempotent Taylor polymorphism and is NP-complete otherwise. More explicitly, we show that for a finite algebra 𝐀 in a congruence modular variety (e.g. for a quasigroup), SysTerm(𝐀) is in P if the core of 𝐀 is abelian and is NP-complete otherwise. Given 𝐀 by the graphs of its basic operations, we show that this condition for tractability can be decided in quasi-polynomial time.

Cite as

Peter Mayr. On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 66:1-66:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{mayr:LIPIcs.MFCS.2023.66,
  author =	{Mayr, Peter},
  title =	{{On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{66:1--66:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.66},
  URN =		{urn:nbn:de:0030-drops-186007},
  doi =		{10.4230/LIPIcs.MFCS.2023.66},
  annote =	{Keywords: systems of equations, general algebras, constraint satisfaction}
}
Document
Extending the Range of C-XSC: Some Tools and Applications for the use in Parallel and other Environments

Authors: Markus Grimmer

Published in: Dagstuhl Seminar Proceedings, Volume 8021, Numerical Validation in Current Hardware Architectures (2008)


Abstract
There is a broad range of packages and libraries for verified numerical computation. C-XSC is a library combining one of the most extensive sets of functions and operations on the one hand with a wide range of applications and special features on the other hand. As such it is an important task both to make use of its existing capabilities in applications and to develop further extensions giving access to additional areas and environments. In this talk, we present some examples of extensions for C-XSC that have been developed lately. Among these are extensions that give access to further hardware and software environments as well as applications making use of these possibilities. Software libraries for interval computation always imply great computation effort: One way to reduce computation times is the development of parallel methods to make use of parallel hardware. For this, it is important that the features and data types of the used library can be easily used in parallel programs. An MPI package for C-XSC data types allows to easily use C-XSC in parallel programs without bothering about the internal structure of data types. Another extension of C-XSC, the C-XSC Taylor arithmetic, is also covered by the MPI package. Parallel verified linear system solvers based on the package are available as well, and further development has been and is being done to integrate more efficient methods for interval linear system solution. One application making use of the mentioned extensions is a parallel verified Fredholm integral equation solver. Some results are given to demonstrate the reduction of computation time and, at the same time, the accuracy gain that can be obtained using the increased computation power. Naturally, hardware interval support would offer still more possibilities towards optimal performance of verified numerical software. Another possibility to extend the range of C-XSC is to make results available for further computations in other software environments as, for example, computer algebra packages. An example of this is presented for the Maple interval package intpakX. This kind of interfaces also allows the user to get access to further platforms like operating systems, compilers or even hardware. References: [1] ALiCEnext: http://www.alicenext.uni-wuppertal.de. [2] Blomquist, F.; Hofschuster, W.; Kraemer, W.: Real and Complex Taylor Arithmetic in C-XSC. Preprint BUW-WRSWT 2005/4, University of Wuppertal, 2005. [3] Grimmer, M.; Kraemer, W.: An MPI Extension for Verified Numerical Computations in Parallel Environments. In: Int. Conf. on Scientific Computing (CSC’07, Worldcomp’07) Las Vegas, June 25-28, 2007, Proceedings pp. 111-117, Arabnia et al. (eds.), 2007. [4] Grimmer, M.: An MPI Extension for the Use of C-XSC in Parallel Environments. Preprint BUW-WRSWT 2005/3, University of Wuppertal, 2005. [5] Grimmer, M.: Selbstverifizierende mathematische Softwarewerkzeuge im High Performance Computing. Dissertation, Logos Verlag, Berlin, 2007. [6] Grimmer, M.: Interval Arithmetic in Maple with intpakX. In: PAMM - Proceedings in Applied Mathematics and Mechanics, Vol. 2, Nr. 1, p. 442-443, Wiley-InterScience, 2003. [7] Hofschuster, W.; Kraemer, W.: C-XSC 2.0: A C++ Library for Extended Scientific Computing. Numerical Software with Result Verification, Lecture Notes in Computer Science, Volume 2991/2004, Springer-Verlag, Heidelberg, pp. 15 - 35, 2004. [8] Klein, W.: Enclosure Methods for Linear and Nonlinear Systems of Fredholm Integral Equations of the Second Kind. In: Adams, Kulisch: Scientific Computing with Result Verification, Academic Press, 1993.

Cite as

Markus Grimmer. Extending the Range of C-XSC: Some Tools and Applications for the use in Parallel and other Environments. In Numerical Validation in Current Hardware Architectures. Dagstuhl Seminar Proceedings, Volume 8021, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{grimmer:DagSemProc.08021.10,
  author =	{Grimmer, Markus},
  title =	{{Extending the Range of C-XSC: Some Tools and Applications for the use in Parallel and other Environments}},
  booktitle =	{Numerical Validation in Current Hardware Architectures},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8021},
  editor =	{Annie Cuyt and Walter Kr\"{a}mer and Wolfram Luther and Peter Markstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08021.10},
  URN =		{urn:nbn:de:0030-drops-14416},
  doi =		{10.4230/DagSemProc.08021.10},
  annote =	{Keywords: C-XSC, Integral Equations, Interval Arithmetic, Maple, MPI, Parallel Environment, Taylor Arithmetic, Verified Linear System Solver.}
}
Document
07461 Abstracts Collection – Numerical Methods for Structured Markov Chains

Authors: Dario A. Bini, Beatrice Meini, Vaidyanathan Ramaswami, Marie-Ange Remiche, and Peter Taylor

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)


Abstract
From 11.11. to 14.11.07, the Dagstuhl Seminar 07461 ``Numerical Methods for Structured Markov Chains'' 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

Dario A. Bini, Beatrice Meini, Vaidyanathan Ramaswami, Marie-Ange Remiche, and Peter Taylor. 07461 Abstracts Collection – Numerical Methods for Structured Markov Chains. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bini_et_al:DagSemProc.07461.1,
  author =	{Bini, Dario A. and Meini, Beatrice and Ramaswami, Vaidyanathan and Remiche, Marie-Ange and Taylor, Peter},
  title =	{{07461 Abstracts Collection – Numerical Methods for Structured Markov Chains}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.1},
  URN =		{urn:nbn:de:0030-drops-14046},
  doi =		{10.4230/DagSemProc.07461.1},
  annote =	{Keywords: Matrix analytic methods, markov processes, queuing theory, numerical methods, structured matrices, telecommunication modeling, performance evaluation}
}
Document
07461 Executive Summary – Numerical Methods for Structured Markov Chains

Authors: Dario A. Bini, Beatrice Meini, Vaidyanathan Ramaswami, Marie-Ange Remiche, and Peter Taylor

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)


Abstract
This Dagstuhl seminar has brought together leaders and young researchers in the fields of analysis of numerical algorithms, applied stochastic modeling and statistical inference, with the result of stimulating exchange of methodologies and experiences and generating synergetic collaborations. This has favored a better communication between these worlds where problems from the applications feed the theoretical research and where advanced numerical tools can be utilized in applications with reciprocal advantages.

Cite as

Dario A. Bini, Beatrice Meini, Vaidyanathan Ramaswami, Marie-Ange Remiche, and Peter Taylor. 07461 Executive Summary – Numerical Methods for Structured Markov Chains. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bini_et_al:DagSemProc.07461.2,
  author =	{Bini, Dario A. and Meini, Beatrice and Ramaswami, Vaidyanathan and Remiche, Marie-Ange and Taylor, Peter},
  title =	{{07461 Executive Summary – Numerical Methods for Structured Markov Chains}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.2},
  URN =		{urn:nbn:de:0030-drops-14006},
  doi =		{10.4230/DagSemProc.07461.2},
  annote =	{Keywords: Matrix analytic methods, Markov processes, queuing theory, numerical methods, structured matrices, telecommunication modeling, performance evaluation.}
}
Document
A policy iteration algorithm for Markov decision processes skip-free in one direction

Authors: Joke Lambert, Benny van Houdt, and Chris Blondia

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)


Abstract
In this paper we present a new algorithm for policy iteration for Markov decision processes (MDP) skip-free in one direction. This algorithm, which is based on matrix analytic methods, is in the same spirit as the algorithm of White (Stochastic Models, 21:785-797, 2005) which was limited to matrices that are skip-free in both directions. Optimization problems that can be solved using Markov decision processes arise in the domain of optical buffers, when trying to improve loss rates of fibre delay line (FDL) buffers. Based on the analysis of such an FDL buffer we present a comparative study between the different techniques available to solve an MDP. The results illustrate that the exploitation of the structure of the transition matrices places us in a position to deal with larger systems, while reducing the computation times.

Cite as

Joke Lambert, Benny van Houdt, and Chris Blondia. A policy iteration algorithm for Markov decision processes skip-free in one direction. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{lambert_et_al:DagSemProc.07461.3,
  author =	{Lambert, Joke and van Houdt, Benny and Blondia, Chris},
  title =	{{A policy iteration algorithm for Markov decision processes skip-free in one direction}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.3},
  URN =		{urn:nbn:de:0030-drops-14032},
  doi =		{10.4230/DagSemProc.07461.3},
  annote =	{Keywords: Markov Decision Process, Policy Evaluation, Skip-Free, Optical buffers, Fibre Delay Lines}
}
Document
Characterizing Coxian Distributions of Algebraic Degree q and Triangular Order p

Authors: Mark Fackrell

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)


Abstract
In this research note we present a procedure to characterize the set of all Coxian distributions of algebraic degree q that have Coxian representations of order p where p > q.

Cite as

Mark Fackrell. Characterizing Coxian Distributions of Algebraic Degree q and Triangular Order p. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{fackrell:DagSemProc.07461.4,
  author =	{Fackrell, Mark},
  title =	{{Characterizing Coxian Distributions of Algebraic Degree q and Triangular Order p}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.4},
  URN =		{urn:nbn:de:0030-drops-13916},
  doi =		{10.4230/DagSemProc.07461.4},
  annote =	{Keywords: Phase-type distribution, Coxian distribution, algebraic degree, triangular order, rational Laplace-Stieltjes transform}
}
Document
Current results and open questions on PH and MAP characterization

Authors: Levente Bodrog, Armin Heindl, Gábor Horváth, Miklós Telek, and András Horváth

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)


Abstract
Stochastic processes with matrix exponential kernels have a wide range of applications due to the availability of efficient matrix analytic methods. The characterization of these processes is in progress in recent years. Basic questions like the flexibility, the degree of freedom, the most efficient (canonical) representation of these models are under study. The presentation collects a set of available results and related open questions.

Cite as

Levente Bodrog, Armin Heindl, Gábor Horváth, Miklós Telek, and András Horváth. Current results and open questions on PH and MAP characterization. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bodrog_et_al:DagSemProc.07461.5,
  author =	{Bodrog, Levente and Heindl, Armin and Horv\'{a}th, G\'{a}bor and Telek, Mikl\'{o}s and Horv\'{a}th, Andr\'{a}s},
  title =	{{Current results and open questions on PH and MAP characterization}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.5},
  URN =		{urn:nbn:de:0030-drops-14010},
  doi =		{10.4230/DagSemProc.07461.5},
  annote =	{Keywords: PH distribution, ME distribution, MAP, MEP}
}
Document
Erlangian Approximation to Finite Time Ruin Probabilities in Perturbed Risk Models

Authors: Kaiqi Yu, David A. Stanford, and Jiandong Ren

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)


Abstract
In this work-in-progress, we consider perturbed risk processes that have an underlying Markovian structure, including Markovian risk processes, and Sparre-Andersen risk processes when both inter claim times and claim sizes are phase-type. We apply the Erlangization method to this risk process in order to obtain an accurate approximation of the finite time ruin probability. In addition, we recognize a repeating structure in the probability matrices we work with. This is the key element in developing more efficent algorithms for the computation of the ruin probabilities. Several numerical examples are present to illustrate the model.

Cite as

Kaiqi Yu, David A. Stanford, and Jiandong Ren. Erlangian Approximation to Finite Time Ruin Probabilities in Perturbed Risk Models. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{yu_et_al:DagSemProc.07461.6,
  author =	{Yu, Kaiqi and Stanford, David A. and Ren, Jiandong},
  title =	{{Erlangian Approximation to Finite Time Ruin Probabilities in Perturbed Risk Models}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.6},
  URN =		{urn:nbn:de:0030-drops-13999},
  doi =		{10.4230/DagSemProc.07461.6},
  annote =	{Keywords: Perturbed risk processes, finite-time ruin probability, phase-type distribution, fluid flow models, Erlangization}
}
Document
From Algebraic Riccati equations to unilateral quadratic matrix equations: old and new algorithms

Authors: Dario A. Bini, Beatrice Meini, and Federico Poloni

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)


Abstract
The problem of reducing an algebraic Riccati equation $XCX-AX-XD+B=0$ to a unilateral quadratic matrix equation (UQME) of the kind $PX^2+QX+R$ is analyzed. New reductions are introduced which enable one to prove some theoretical and computational properties. In particular we show that the structure preserving doubling algorithm of B.D.O. Anderson [Internat. J. Control, 1978] is nothing else but the cyclic reduction algorithm applied to a suitable UQME. A new algorithm obtained by complementing our reductions with the shrink-and-shift tech- nique of Ramaswami is presented. Finally, faster algorithms which require some non-singularity conditions, are designed. The non-singularity re- striction is relaxed by introducing a suitable similarity transformation of the Hamiltonian.

Cite as

Dario A. Bini, Beatrice Meini, and Federico Poloni. From Algebraic Riccati equations to unilateral quadratic matrix equations: old and new algorithms. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bini_et_al:DagSemProc.07461.7,
  author =	{Bini, Dario A. and Meini, Beatrice and Poloni, Federico},
  title =	{{From Algebraic Riccati equations to unilateral quadratic matrix equations: old and new algorithms}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--28},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.7},
  URN =		{urn:nbn:de:0030-drops-13987},
  doi =		{10.4230/DagSemProc.07461.7},
  annote =	{Keywords: Algebraic Riccati Equation, Matrix Equation, Cyclic Reduction, Structured doubling algorithm}
}
Document
Interarrival Times Characterization and Fitting for Markovian Traffic Analysis

Authors: Giuliano Casale, Eddy Z. Zhang, and Evgenia Smirni

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)


Abstract
We propose a traffic fitting algorithm for Markovian Arrival Processes (MAPs) that can capture statistics of any order of interarrival times. By studying real traffic traces, we show that matching higher order properties, in addition to first and second order descriptors, results in increased queueing prediction accuracy with respect to other algorithms that only match the mean, coefficient of variation, and autocorrelations. The result promotes the idea of modeling traffic traces using the interarrival time process instead of the counting process that is more frequently employed in previous work, but for which higher order moments are difficult to manipulate. We proceed by first characterizing the general properties of MAPs using a spectral approach. Based on this characterization, we show how different MAP processes can be combined together using Kronecker products to define a larger MAP with predefined properties of interarrival times. We then devise an algorithm that is based on this Kronecker composition and can accurately fit traffic traces. The algorithm employs nonlinear optimization programs that can be customized to fit an arbitrary number of moments and to meet the desired cost-accuracy tradeoff. Numerical results of the fitting algorithm on real HTTP and TCP traffic data, such as the Bellcore Aug89 trace, indicate that the proposed fitting methods achieve increased prediction accuracy with respect to other state-of-the-art fitting methods.

Cite as

Giuliano Casale, Eddy Z. Zhang, and Evgenia Smirni. Interarrival Times Characterization and Fitting for Markovian Traffic Analysis. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{casale_et_al:DagSemProc.07461.8,
  author =	{Casale, Giuliano and Zhang, Eddy Z. and Smirni, Evgenia},
  title =	{{Interarrival Times Characterization and Fitting for Markovian Traffic Analysis}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.8},
  URN =		{urn:nbn:de:0030-drops-13908},
  doi =		{10.4230/DagSemProc.07461.8},
  annote =	{Keywords: MAP fitting, interarrival time process, higher-order moments}
}
Document
Matrix Analytic Methods in Branching processes

Authors: Sophie Hautphenne, Guy Latouche, and Marie-Ange Remiche

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)


Abstract
We examine the question of solving the extinction probability of a particular class of continuous-time multi-type branching processes, named Markovian binary trees (MBT). The extinction probability is the minimal nonnegative solution of a fixed point equation that turns out to be quadratic, which makes its resolution particularly clear. We analyze first two linear algorithms to compute the extinction probability of an MBT, of which one is new, and, we propose a quadratic algorithm arising from Newton's iteration method for fixed-point equations. Finally, we add a catastrophe process to the initial MBT, and we analyze the resulting system. The extinction probability turns out to be much more difficult to compute; we use a $G/M/1$-type Markovian process approach to approximate this probability.

Cite as

Sophie Hautphenne, Guy Latouche, and Marie-Ange Remiche. Matrix Analytic Methods in Branching processes. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{hautphenne_et_al:DagSemProc.07461.9,
  author =	{Hautphenne, Sophie and Latouche, Guy and Remiche, Marie-Ange},
  title =	{{Matrix Analytic Methods in Branching processes}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.9},
  URN =		{urn:nbn:de:0030-drops-13935},
  doi =		{10.4230/DagSemProc.07461.9},
  annote =	{Keywords: Branching Processes, Matrix Analytic Methods, Extinction Probability, Catastrophe Process}
}
Document
Multivariate matrix-exponential distributions

Authors: Mogens Bladt and Bo Friis Nielsen

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)


Abstract
We review what is currently known about one-dimensional distributions on the non-negative reals with rational Laplace transform, also known as matrix-exponential distributions. In particular we discuss a flow interpreation which enables one to mimic certain probabilisticly inspired arguments which are known from the theory of phase-type distributions. We then move on to present ongoing research for higher dimensions. We discuss a characterization result, some closure properties, and a number of examples. Finally we present open problems and future perspectives.

Cite as

Mogens Bladt and Bo Friis Nielsen. Multivariate matrix-exponential distributions. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bladt_et_al:DagSemProc.07461.10,
  author =	{Bladt, Mogens and Nielsen, Bo Friis},
  title =	{{Multivariate matrix-exponential distributions}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.10},
  URN =		{urn:nbn:de:0030-drops-13975},
  doi =		{10.4230/DagSemProc.07461.10},
  annote =	{Keywords: Multivariate matrix-exponential distributions, multivariate phase-type distributions, rational Laplace transform}
}
Document
Nonsymmetric algebraic Riccati equations associated with an M-matrix: recent advances and algorithms

Authors: Dario A. Bini, Bruno Iannazzo, Beatrice Meini, and Federico Poloni

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)


Abstract
We survey on theoretical properties and algorithms concerning the problem of solving a nonsymmetric algebraic Riccati equation, and we report on some known methods and new algorithmic advances. In particular, some results on the number of positive solutions are proved and a careful convergence analysis of Newton's iteration is carried out in the cases of interest where some singularity conditions are encountered. From this analysis we determine initial approximations which still guarantee the quadratic convergence.

Cite as

Dario A. Bini, Bruno Iannazzo, Beatrice Meini, and Federico Poloni. Nonsymmetric algebraic Riccati equations associated with an M-matrix: recent advances and algorithms. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bini_et_al:DagSemProc.07461.11,
  author =	{Bini, Dario A. and Iannazzo, Bruno and Meini, Beatrice and Poloni, Federico},
  title =	{{Nonsymmetric algebraic Riccati equations associated with an M-matrix: recent advances and algorithms}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--31},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.11},
  URN =		{urn:nbn:de:0030-drops-13958},
  doi =		{10.4230/DagSemProc.07461.11},
  annote =	{Keywords: Nonsymmetric algebraic Riccati equations, matrix equation, M-matrices, Newton method, quadratically convergent algorithms, cyclic reduction, doubling}
}
Document
On the Properties of Moments of Matrix Exponential Distributions and Matrix Exponential Processes

Authors: Levente Bodrog, András Horváth, and Miklós Telek

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)


Abstract
In this paper we provide properties of moments of matrix exponential distributions and joint moments of matrix exponential processes. Based on the provided properties, an algorithm is presented to compute any finite dimensional moments of these processes based on a set of required (low order) moments. This algorithm does not require the computation of any representation of the given process. We present some related examples to demonstrate the potential use of the properties of moments.

Cite as

Levente Bodrog, András Horváth, and Miklós Telek. On the Properties of Moments of Matrix Exponential Distributions and Matrix Exponential Processes. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bodrog_et_al:DagSemProc.07461.12,
  author =	{Bodrog, Levente and Horv\'{a}th, Andr\'{a}s and Telek, Mikl\'{o}s},
  title =	{{On the Properties of Moments of Matrix Exponential Distributions and Matrix Exponential Processes}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.12},
  URN =		{urn:nbn:de:0030-drops-13943},
  doi =		{10.4230/DagSemProc.07461.12},
  annote =	{Keywords: Matrix exponential process, Markov arrival process, Matrix exponential distribution, phase type distribution}
}
Document
On the tail decay of M/G/1-type Markov renewal processes

Authors: Dario A. Bini, Beatrice Meini, and Vaidyanathan Ramaswami

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)


Abstract
The tail decay of M/G/1-type Markov renewal processes is studied. The Markov renewal process is transformed into a Markov chain so that the problem of tail decay is reformulated in terms of the decay of the coefficients of a suitable power series. The latter problem is reduced to analyze the analyticity domain of the power series.

Cite as

Dario A. Bini, Beatrice Meini, and Vaidyanathan Ramaswami. On the tail decay of M/G/1-type Markov renewal processes. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{bini_et_al:DagSemProc.07461.13,
  author =	{Bini, Dario A. and Meini, Beatrice and Ramaswami, Vaidyanathan},
  title =	{{On the tail decay of M/G/1-type Markov renewal processes}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.13},
  URN =		{urn:nbn:de:0030-drops-13966},
  doi =		{10.4230/DagSemProc.07461.13},
  annote =	{Keywords: Renewal processes, tail decay, M/G/1-type Markov chains}
}
  • Refine by Author
  • 5 Bini, Dario A.
  • 5 Meini, Beatrice
  • 3 Ramaswami, Vaidyanathan
  • 3 Remiche, Marie-Ange
  • 2 Bodrog, Levente
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 2 Matrix analytic methods
  • 2 numerical methods
  • 2 queuing theory
  • 2 structured matrices
  • 2 telecommunication modeling
  • Show More...

  • Refine by Type
  • 18 document

  • Refine by Publication Year
  • 16 2008
  • 1 2006
  • 1 2023

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