Displaying similar documents to “Bouquets of circles for lamination languages and complexities”

Automata-based Representations for Infinite Graphs

Salvatore La Torre, Margherita Napoli (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

New compact representations of infinite graphs are investigated. Finite automata are used to represent labelled hyper-graphs which can be also multi-graphs. Our approach consists of a general framework where vertices are represented by a regular prefix-free language and edges are represented by a regular language and a function over tuples. We consider three different functions over tuples: given a tuple the first function returns its first difference, the second one returns...

Traces of term-automatic graphs

Antoine Meyer (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

In formal language theory, many families of languages are defined using either grammars or finite acceptors. For instance, context-sensitive languages are the languages generated by growing grammars, or equivalently those accepted by Turing machines whose work tape's size is proportional to that of their input. A few years ago, a new characterisation of context-sensitive languages as the sets of traces, or path labels, of rational graphs (infinite graphs defined by sets of finite-state...

On the classes of languages accepted by limited context restarting automata

Friedrich Otto, Peter Černo, František Mráz (2014)

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

Similarity:

In the literature various types of restarting automata have been studied that are based on contextual rewriting. A word is accepted by such an automaton if, starting from the initial configuration that corresponds to input , the word is reduced to the empty word by a finite number of applications of these contextual rewritings. This approach is reminiscent of the notion of McNaughton families of languages. Here we put the aforementioned types of restarting automata into the context...

Minimum convex-cost tension problems on series-parallel graphs

Bruno Bachelet, Philippe Mahey (2010)

RAIRO - Operations Research

Similarity:

We present briefly some results we obtained with known methods to solve minimum cost tension problems, comparing their performance on non-specific graphs and on series-parallel graphs. These graphs are shown to be of interest to approximate many tension problems, like synchronization in hypermedia documents. We propose a new method to solve the minimum convex piecewise linear cost tension problem on series-parallel graphs in operations.