Page 1 Next

Displaying 1 – 20 of 86

Showing per page

A generalization of traces

Walter Vogler (1991)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

A Markovian concurrency measure

Dominique Geniet, René Schott, Loÿs Thimonier (1996)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

A note on Coinduction and Weak Bisimilarity for While Programs

J. J.M.M. Rutten (2010)

RAIRO - Theoretical Informatics and Applications

An illustration of coinduction in terms of a notion of weak bisimilarity is presented. First, an operational semantics 𝒪 for while programs is defined in terms of a final automaton. It identifies any two programs that are weakly bisimilar, and induces in a canonical manner a compositional model 𝒟 . Next 𝒪 = 𝒟 is proved by coinduction.

A survey on combinatorial optimization in dynamic environments∗

Nicolas Boria, Vangelis T. Paschos (2011)

RAIRO - Operations Research

This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The...

A survey on combinatorial optimization in dynamic environments∗

Nicolas Boria, Vangelis T. Paschos (2011)

RAIRO - Operations Research

This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The...

An upper bound for transforming self-verifying automata into deterministic ones

Ira Assent, Sebastian Seibert (2007)

RAIRO - Theoretical Informatics and Applications

This paper describes a modification of the power set construction for the transformation of self-verifying nondeterministic finite automata to deterministic ones. Using a set counting argument, the upper bound for this transformation can be lowered from 2 n to O ( 2 n n ) .

Automata with modulo counters and nondeterministic counter bounds

Daniel Reidenbach, Markus L. Schmid (2014)

Kybernetika

We introduce and investigate Nondeterministically Bounded Modulo Counter Automata (NBMCA), which are two-way multi-head automata that comprise a constant number of modulo counters, where the counter bounds are nondeterministically guessed, and this is the only element of nondeterminism. NBMCA are tailored to recognising those languages that are characterised by the existence of a specific factorisation of their words, e. g., pattern languages. In this work, we subject NBMCA to a theoretically sound...

Binary operations on automatic functions

Juhani Karhumäki, Jarkko Kari, Joachim Kupke (2007)

RAIRO - Theoretical Informatics and Applications

Real functions on the domain [0,1)n – often used to describe digital images – allow for different well-known types of binary operations. In this note, we recapitulate how weighted finite automata can be used in order to represent those functions and how certain binary operations are reflected in the theory of these automata. Different types of products of automata are employed, including the seldomly-used full Cartesian product. We show, however, the infeasibility of functional composition; simple...

Binary operations on automatic functions

Juhani Karhumäki, Jarkko Kari, Joachim Kupke (2008)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Real functions on the domain [ 0 , 1 ) n – often used to describe digital images – allow for different well-known types of binary operations. In this note, we recapitulate how weighted finite automata can be used in order to represent those functions and how certain binary operations are reflected in the theory of these automata. Different types of products of automata are employed, including the seldomly-used full cartesian product. We show, however, the infeasibility of functional composition; simple examples...

Bisimulation on speed: Lower time bounds

Gerald Lüttgen, Walter Vogler (2010)

RAIRO - Theoretical Informatics and Applications

More than a decade ago, Moller and Tofts published their seminal work on relating processes, which are annotated with lower time bounds, with respect to speed. Their paper has left open many questions regarding the semantic theory for the suggested bisimulation-based faster-than preorder, the MT-preorder, which have not been addressed since. The encountered difficulties concern a general compositionality result, a complete axiom system for finite processes, a convincing intuitive justification...

Bisimulation on speed : lower time bounds

Gerald Lüttgen, Walter Vogler (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

More than a decade ago, Moller and Tofts published their seminal work on relating processes, which are annotated with lower time bounds, with respect to speed. Their paper has left open many questions regarding the semantic theory for the suggested bisimulation-based faster-than preorder, the MT-preorder, which have not been addressed since. The encountered difficulties concern a general compositionality result, a complete axiom system for finite processes, a convincing intuitive justification of...

Characteristic Formulae for Timed Automata

Luca Aceto, Anna Ingólfsdóttir, Mikkel Lykke Pedersen, Jan Poulsen (2010)

RAIRO - Theoretical Informatics and Applications

This paper offers characteristic formula constructions in the real-time logic Lν for several behavioural relations between (states of) timed automata. The behavioural relations studied in this work are timed (bi)similarity, timed ready simulation, faster-than bisimilarity and timed trace inclusion. The characteristic formulae delivered by our constructions have size which is linear in that of the timed automaton they logically describe. This also applies to the characteristic formula for...

Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs

Henrik Brosenne, Matthias Homeister, Stephan Waack (2010)

RAIRO - Theoretical Informatics and Applications

We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear code functions. The...

Characterizing the complexity of boolean functions represented by well-structured graph-driven parity-FBDDs

Henrik Brosenne, Matthias Homeister, Stephan Waack (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear code functions....

Currently displaying 1 – 20 of 86

Page 1 Next