The Experts below are selected from a list of 11856 Experts worldwide ranked by ideXlab platform
Manfred Droste - One of the best experts on this subject based on the ideXlab platform.
-
Semirings and Formal Power Series
Monographs in Theoretical Computer Science, 2009Co-Authors: Manfred Droste, Werner KuichAbstract:This chapter presents basic foundations for the theory of weighted automata: semirings and Formal Power Series. A fundamental question is how to extend the star operation (Kleene iteration) from languages to Series. For this, we investigate ordered, complete and continuous semirings and the related concepts of star semirings and Conway semirings. We derive natural properties for the Kleene star of cycle-free Series and also of matrices often used to analyze the behavior of weighted automata. Finally, we investigate cycle-free linear equations which provide a useful tool for proving identities for Formal Power Series.
-
on aperiodic and star free Formal Power Series in partially commuting variables
Theory of Computing Systems \ Mathematical Systems Theory, 2008Co-Authors: Manfred Droste, Paul GastinAbstract:Formal Power Series over non-commuting variables have been investigated as representations of the behavior of automata with multiplicities. Here we introduce and investigate the concepts of aperiodic and of star-free Formal Power Series over semirings and partially commuting variables. We prove that if the semiring K is idempotent and commutative, or if K is idempotent and the variables are non-commuting, then the product of any two aperiodic Series is again aperiodic. We also show that if K is idempotent and the matrix monoids over K have a Burnside property (satisfied, e.g. by the tropical semiring), then the aperiodic and the star-free Series coincide. This generalizes a classical result of Schutzenberger (Inf. Control 4:245–270, 1961) for aperiodic regular languages and subsumes a result of Guaiana et al. (Theor. Comput. Sci. 97:301–311, 1992) on aperiodic trace languages.
-
Skew and infinitary Formal Power Series
Theoretical Computer Science, 2006Co-Authors: Manfred Droste, Dietrich KuskeAbstract:We investigate finite-state systems with weights. Departing from the classical theory, in this paper the weight of an action does not only depend on the state of the system, but also on the time when it is executed; this reflects the usual human evaluation practices in which later events are considered less urgent and carry less weight than close events. We first characterize the terminating behaviors of such systems in terms of rational Formal Power Series. This generalizes a classical result of Schutzenberger. Secondly, we deal with nonterminating behaviors and their weights. This includes an extension of the Buchi-acceptance condition from finite automata to weighted automata and provides a characterization of these nonterminating behaviors in terms of ω-rational Formal Power Series. This generalizes a classical theorem of Buchi.
-
On transformations of Formal Power Series
Information & Computation, 2003Co-Authors: Manfred Droste, Guo-qiang ZhangAbstract:Formal Power Series are an extension of Formal languages. Recognizable Formal Power Series can be captured by the so-called weighted finite automata, generalizing finite state machines. In this paper, motivated by codings of Formal languages, we introduce and investigate two types of transformations for Formal Power Series. We characterize when these transformations preserve recognizability, generalizing the recent results of Zhang [16] to the Formal Power Series setting. We show, for example, that the "square-root" operation, while preserving regularity for Formal languages, preserves recognizability for Formal Power Series when the underlying semiring is commutative or locally finite, but not in general.
-
skew and infinitary Formal Power Series
International Colloquium on Automata Languages and Programming, 2003Co-Authors: Manfred Droste, Dietrich KuskeAbstract:We investigate finite-state systems with costs. Departing from classical theory, in this paper the cost of an action does not only depend on the state of the system, but also on the time when it is executed. We first characterize the terminating behaviors of such systems in terms of rational Formal Power Series. This generalizes a classical result of Schutzenberger. Using the previous results, we also deal with nonterminating behaviors and their costs. This includes an extension of the Buchi-acceptance condition from finite automata to weighted automata and provides a characterization of these nonterminating behaviors in terms of ω-rational Formal Power Series. This generalizes a classical theorem of Buchi.
Jan H Van Schuppen - One of the best experts on this subject based on the ideXlab platform.
-
partial realization theory for linear switched systems a Formal Power Series approach
Automatica, 2011Co-Authors: Mihaly Petreczky, Jan H Van SchuppenAbstract:The paper presents partial-realization theory and a realization algorithm for linear switched systems. The results are similar to partial-realization theory of linear and bilinear systems. Our main tool is the theory of rational Formal Power Series.
Mihaly Petreczky - One of the best experts on this subject based on the ideXlab platform.
-
partial realization theory for linear switched systems a Formal Power Series approach
Automatica, 2011Co-Authors: Mihaly Petreczky, Jan H Van SchuppenAbstract:The paper presents partial-realization theory and a realization algorithm for linear switched systems. The results are similar to partial-realization theory of linear and bilinear systems. Our main tool is the theory of rational Formal Power Series.
-
Hybrid Formal Power Series and Their Application to Realization Theory of Hybrid Systems
2006Co-Authors: Mihaly PetreczkyAbstract:The paper presents the abstract framework of hybrid Formal Power Series. Hybrid Formal Power Series are analogous to non-commutative Formal Power Series. Formal Power Series are widely used in control systems theory. In particular, theory of Formal Power Series is the main tool for solving the realization problem for linear and bilinear control systems. The theory of hybrid Formal Power Series developed in this paper plays a similar role in realization theory of hybrid systems. The paper develops theory of rational hybrid Formal Power Series and their representations. The relevance of the abstract theory is demonstrated by presenting an application of the theory to solving the realization problem for linear and bilinear hybrid systems.
Dietrich Kuske - One of the best experts on this subject based on the ideXlab platform.
-
Schützenberger's theorem on Formal Power Series follows from Kleene's theorem
Theoretical Computer Science, 2008Co-Authors: Dietrich KuskeAbstract:We derive Schutzenberger's characterisation of the set of recognizable Formal Power Series as a Formal corollary from Kleene's characterisation of the set of regular languages.
-
Schützenberger’s theorem on Formal Power Series follows from Kleene’s theorem
Theoretical Computer Science, 2008Co-Authors: Dietrich KuskeAbstract:AbstractWe derive Schützenberger’s characterisation of the set of recognizable Formal Power Series as a Formal corollary from Kleene’s characterisation of the set of regular languages
-
Skew and infinitary Formal Power Series
Theoretical Computer Science, 2006Co-Authors: Manfred Droste, Dietrich KuskeAbstract:We investigate finite-state systems with weights. Departing from the classical theory, in this paper the weight of an action does not only depend on the state of the system, but also on the time when it is executed; this reflects the usual human evaluation practices in which later events are considered less urgent and carry less weight than close events. We first characterize the terminating behaviors of such systems in terms of rational Formal Power Series. This generalizes a classical result of Schutzenberger. Secondly, we deal with nonterminating behaviors and their weights. This includes an extension of the Buchi-acceptance condition from finite automata to weighted automata and provides a characterization of these nonterminating behaviors in terms of ω-rational Formal Power Series. This generalizes a classical theorem of Buchi.
-
skew and infinitary Formal Power Series
International Colloquium on Automata Languages and Programming, 2003Co-Authors: Manfred Droste, Dietrich KuskeAbstract:We investigate finite-state systems with costs. Departing from classical theory, in this paper the cost of an action does not only depend on the state of the system, but also on the time when it is executed. We first characterize the terminating behaviors of such systems in terms of rational Formal Power Series. This generalizes a classical result of Schutzenberger. Using the previous results, we also deal with nonterminating behaviors and their costs. This includes an extension of the Buchi-acceptance condition from finite automata to weighted automata and provides a characterization of these nonterminating behaviors in terms of ω-rational Formal Power Series. This generalizes a classical theorem of Buchi.
-
ICALP - Skew and infinitary Formal Power Series
Automata Languages and Programming, 2003Co-Authors: Manfred Droste, Dietrich KuskeAbstract:We investigate finite-state systems with costs. Departing from classical theory, in this paper the cost of an action does not only depend on the state of the system, but also on the time when it is executed. We first characterize the terminating behaviors of such systems in terms of rational Formal Power Series. This generalizes a classical result of Schutzenberger. Using the previous results, we also deal with nonterminating behaviors and their costs. This includes an extension of the Buchi-acceptance condition from finite automata to weighted automata and provides a characterization of these nonterminating behaviors in terms of ω-rational Formal Power Series. This generalizes a classical theorem of Buchi.
W. Balser - One of the best experts on this subject based on the ideXlab platform.
-
Summability of Formal Power Series of Ordinary and Partial Differential Equations
Functional differential equations, 2004Co-Authors: W. BalserAbstract:In this article we shall briefly describe the theory of multisummability of Formal Power Series and discuss its application in different areas of analysis, such as ordinary and partial differential equations as well as difference equations.
-
Multisummability of Formal Power Series solutions of linear ordinary differential equations
Asymptotic Analysis, 1991Co-Authors: W. Balser, B.l.j. Braaksma, J.-p. Ramis, Yasutaka SibuyaAbstract:27 Balser, W., B.L.J. Braaksma, J.-P. Ramis and Y. Sibuya, Multisummability of Formal Power Series solutions of linear ordinary differential equations, Asymptotic Analysis 5 (1991) 27-45. If I is a Formal Power Series solution of a linear meromorphic differential equation, then it is shown that 1=11 + ... + Iq, were fj is hrsummable; here h 1, .•• , hq are slopes of the associated Newton polygon. The multisummability properties of fundamental solutions of linear homogeneous meromorphic differential equations are studied.