Results 1 to 10 of about 841,154 (197)
Pumping lemmas for weighted automata [PDF]
Logical Methods in Computer Science, 2021 We present pumping lemmas for five classes of functions definable by fragments of weighted automata over the min-plus semiring, the max-plus semiring and the semiring of natural numbers. As a corollary we show that the hierarchy of functions definable by
Agnishom Chattopadhyay +3 more
doaj +3 more sources
Coalgebras for Bisimulation of Weighted Automata over Semirings [PDF]
Logical Methods in Computer Science, 2023 Weighted automata are a generalization of nondeterministic automata that associate a weight drawn from a semiring $K$ with every transition and every state.
Purandar Bhaduri
doaj +3 more sources
Bideterministic Weighted Automata
Information and Computation, 2022 A finite automaton is called bideterministic if it is both deterministic and codeterministic -- that is, if it is deterministic and its transpose is deterministic as well. The study of such automata in a weighted setting is initiated. All trim bideterministic weighted automata over integral domains and over positive semirings are proved to be minimal ...
Peter Kostolányi
openaire +4 more sources
Synchronizing weighted automata [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 We introduce two generalizations of synchronizability to automata with transitions weighted in an arbitrary semiring K=(K,+,*,0,1). (or equivalently, to finite sets of matrices in K^nxn.) Let us call a matrix A location-synchronizing if there exists a ...
Szabolcs Iván
doaj +4 more sources
Morphisms and minimisation of weighted automata [PDF]
Fundamenta Informaticae, 2022 This paper studies the algorithms for the minimisation of weighted automata. It starts with the definition of morphisms-which generalises and unifies the notion of bisimulation to the whole class of weighted automata-and the unicity of a minimal quotient for every automaton, obtained by partition refinement.
Lombardy, Sylvain, Sakarovitch, Jacques
openaire +5 more sources
Feasability of Learning Weighted Automata on a Semiring [PDF]
Logical Methods in Computer Science, 2023 Since the seminal work by Angluin and the introduction of the L*-algorithm, active learning of automata by membership and equivalence queries has been extensively studied to learn various extensions of automata.
Laure Daviaud, Marianne Johnson
doaj +2 more sources
Containment and Equivalence of Weighted Automata: Probabilistic and Max-Plus Cases [PDF]
Language and Automata Theory and Applications14th International Conference, 2020 This paper surveys some results regarding decision problems for probabilistic and max-plus automata, such as containment and equivalence. Probabilistic and max-plus automata are part of the general family of weighted automata, whose semantics are maps ...
Daviaud L.
europepmc +2 more sources
Pebble Weighted Automata and Weighted Logics [PDF]
ACM Transactions on Computational Logic, 2014 We introduce new classes of weighted automata on words. Equipped with pebbles, they go beyond the class of recognizable formal power series: they capture weighted first-order logic enriched with a quantitative version of transitive closure. In contrast to previous work, this calculus allows for unrestricted use of existential and universal ...
Benedikt Bollig, Benjamin Monmege
exaly +3 more sources
Approximation of Weighted Automata with Storage [PDF]
Electronic Proceedings in Theoretical Computer Science, 2017 We use a non-deterministic variant of storage types to develop a framework for the approximation of automata with storage. This framework is used to provide automata-theoretic views on the approximation of multiple context-free languages and on coarse ...
Tobias Denkinger
doaj +4 more sources
Efficient Completion of Weighted Automata [PDF]
Electronic Proceedings in Theoretical Computer Science, 2016 We consider directed graphs with edge labels from a semiring. We present an algorithm that allows efficient execution of queries for existence and weights of paths, and allows updates of the graph: adding nodes and edges, and changing weights of ...
Johannes Waldmann
doaj +4 more sources