Concept

Weighted automaton

Related publications (14)

Lower Bounds for Unambiguous Automata via Communication Complexity

We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. 1) Complement: There is a language L recognised by an n-state UFA such that the complement language ̅L ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022

On verifying causal consistency

Rachid Guerraoui, Jad Hamza

Causal consistency is one of the most adopted consistency criteria for distributed implementations of data structures. It ensures that operations are executed at all sites according to their causal precedence. We address the issue of verifying automaticall ...

Measuring and Synthesizing Systems in Probabilistic Environments

Barbara Jobstmann, Rishabh Singh

The traditional synthesis question given a specification asks for the automatic construction of a system that satisfies the specification, whereas often there exists a preference order among the different systems that satisfy the given specification. Under ...

Assoc Computing Machinery2015

Formalization, Implementation, and Modeling of Institutional Controllers for Distributed Robotic Systems

Alcherio Martinoli, José Nuno Ferreira Maia Pereira

The work described is part of a long term program of introducing institutional robotics, a novel framework for the coordination of robot teams that stems from institutional economics concepts. Under the framework, institutions are cumulative sets of persis ...

2014

Symbolic execution of Reo circuits using constraint automata

Hossein Hojjat

Reo is a coordination language that can be used to model different systems. We propose a technique for symbolic execution of Reo circuits using the symbolic representation of data constraints in Constraint Automata. This technique enables us to obtain the ...

2012

Quasi-Static Scheduling of CAL Actor Networks for Reconfigurable Video Coding

Marco Mattavelli, Christophe Lucarz, Jani Boutellier

The upcoming Reconﬁgurable Video Coding (RVC) standard from MPEG (ISO / IEC SC29WG11) deﬁnes a library of coding tools to specify existing or new compressed video formats and decoders. The coding tool library has been written in a dataﬂow/actor- oriented l ...

2011

Wavelets on graphs via spectral graph theory

Pierre Vandergheynst, Rémi Gribonval

We propose a novel method for constructing wavelet transforms of functions defined on the vertices of an arbitrary finite weighted graph. Our approach is based on defining scaling using the the graph analogue of the Fourier domain, namely the spectral deco ...

Elsevier2011

Quantitative Languages

Laurent Doyen

Quantitative generalizations of classical languages, which assign to each word a real number instead of a Boolean value, have applications in modeling resource-constrained computation. We use weighted automata (finite automata with transition weights) to d ...

2010

Expressiveness And Closure Properties For Quantitative Languages

Laurent Doyen

Weighted automata are nondeterministic automata with numerical weights on transitions. They can define quantitative languages L that assign to each word w a real number L(w). In the case of infinite words, the value of a run is naturally computed as the ma ...

2010

Equivalence of labeled Markov chains

Laurent Doyen

We consider the equivalence problem for labeled Markov chains (LMCs), where each state is labeled with an observation. Two LMCs are equivalent if every finite sequence of observations has the same probability of occurrence in the two LMCs. We show that equ ...

2008

Scheduling Of Dataflow Models Within The Reconfigurable Video Coding Framework

Marco Mattavelli, Christophe Lucarz, Jani Boutellier

The upcoming Reconfigurable Video Coding (RVC) standard from MPEG (ISO/IEC SC29WG11) defines a library of coding tools to specify existing or new compressed video formats and decoders. The coding tool library has been written in a dataflow/actor-oriented l ...

IEEE2008

Scheduling Of Dataflow Models Within The Reconfigurable Video Coding Framework

Marco Mattavelli, Christophe Lucarz, Jani Boutellier

2008

Soundness and Equivalence of Petri Nets and Annotated Finite State Automate: A Comparison in the SOA Context

A lot of work exists on notions of equivalence and soundness relations of different workflow models, which are used in different domains like e.g. Business Process Modeling, Software and Service Engineering. These definitions are based on different models, ...

IEEE2007

Service specification verification and validation for the intelligent network

New architectures of telecommunications networks like the Intelligent Network (IN) proposal allow an ever easier way to introduce new services into a network. However, this facility and the short delays that can be achieved between the first informal speci ...

EPFL1995