The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We consider collage grammars whose rules subdivide the unit square into smaller and smaller rectangles. The decidability status of selected decision problems for this type of grammars is surveyed: the membership problem, the emptiness and finiteness problems, connectedness and disconnectedness of the generated pictures, and the question whether a generated collage contains a rectangle whose lower-left...
Quantitative aspects of systems can be modeled by weighted automata. Here, we deal with such automata running on finite trees. Usually, transitions are weighted with elements of a semiring and the behavior of the automaton is obtained by multiplying the weights along a run. We turn to a more general cost model: the weight of a run is now determined by a global valuation function. An example of such...
A Conway semiring is a semiring S equipped with a unary operation *:S → S, called “star”, satisfying the sum star and product star identities. A Conway semiring-semimodule pair consists of a Conway semiring S and a left S-semimodule V together with a function ω: S → V, called “omega power”, subject to the sum omega and product omega identities. A Kleene type theorem holds...
Partial Conway theories are algebraic theories equipped with a partially defined dagger operation satisfying some natural identities. We prove a Kleene type theorem for partial Conway theories and discuss several applications of this result.
In this paper we consider transformations on formal power series and extend well-known results in terms of homomorphisms to rational functions. Using these results we prove a Kleene-Schützenberger Theorem for formal power series over rational monoids. It extends a result of Sakarovitch.
We consider systems of equations of polynomial weighted tree transformations over the max-plus (or: arctic) semiring ℝ max = ( ℝ + ∪ { − ∞ }, max , + , − ∞ ,0). We apply discounting with a parameter 0 ≤ d < 1 in order to guarantee the existence of the least solution, called least d-solution, of such systems. We compute least d-solutions under u-substitution mode, where u = [IO] or u = OI. We...
In the first part of this survey paper, the notions of finite automata and regular languages are reviewed from various points of view. The middle part contains an introduction to the Hilbert space formalism of finite-level quantum systems, and the final part is a presentation of the most notable quantum finite automata models introduced up to date.
Automata operating on arbitrary graphs were introduced in a previous paper by virtue of a particular instance of an abelian relational graphoid. As it is indicated in the same paper, in order to construct a graph automaton it is necessary and sufficient that the relations over the Kleene star of the state set constitute a graphoid. In this respect, various different versions of graph automata arise...
Picture walking automata were introduced by M. Blum and C. Hewitt in 1967 as a generalization of one-dimensional two-way finite automata to recognize pictures, or two-dimensional words. Several variants have been investigated since then, including deterministic, non-deterministic and alternating transition rules; four-, three- and two-way movements; single- and multi-headed variants; automata that...
In this survey we consider three kinds of algorithmic questions concerning varieties of semigroups. We are interested in identity problems, in the solvability of a system of equations and in the structure of all solutions of a given system. We study them in significant varieties of semigroups, monoids, groups, completely simple semigroups, completely regular semigroups (in particular semigroups satisfying...
This survey paper serves two purposes: Firstly, we consider cycle-free algebraic systems (with respect to a given strong convergence) as a generalization of the usually considered proper systems (with respect to the discrete convergence). Secondly, we develop in a parallel manner the theory of these cycle-free algebraic systems over an arbitrary semiring and the theory of arbitrary algebraic systems...
In this paper, we report on applications of weighted automata in the theory of automatic structures. All (except one) result were known before, but their proof using weighted automata is novel. More precisely, we prove that the extension of first-order logic by the infinity ∃ ∞ , the modulo ∃ (p,q), and the (new) boundedness quantifier is decidable. The first two quantifiers are handled using...
In this survey (functional) compositions of weighted tree transformations computable by weighted extended top-down tree transducers are investigated. The existing results in the literature are explained and illustrated. It is argued, why certain compositions are not possible in the general case, and 3 informed conjectures provide an insight into potentially 3 new composition results that extend and...
We study Kleene’s theorem about the equivalence of automata and expressions in a quantitative setting both for finite and infinite words. The quantities originate from valuation monoids and ω-indexed valuation monoids which cover not only semirings but also cost models like average cost, long-run peaks of resource consumption, or discounting sums of rewards. For finite words we deduce the characterization...
Consider a universal set and a vertex set V and suppose that to each vertex in V we assign independently a subset of chosen at random according to some probability distribution over subsets of . By connecting two vertices if their assigned subsets have elements in common, we get a random instance of a random intersection graphs model. In this work, we overview...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.