All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1

Displaying 1 – 15 of 15

Showing per page

A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy : Part II

Jérémie Cabessa, Jacques Duparc (2009)

RAIRO - Theoretical Informatics and Applications

The algebraic counterpart of the Wagner hierarchy consists of a well-founded and decidable classification of finite pointed ω-semigroups of width 2 and height ωω. This paper completes the description of this algebraic hierarchy. We first give a purely algebraic decidability procedure of this partial ordering by introducing a graph representation of finite pointed ω-semigroups allowing to compute their precise Wagner degrees. The Wagner degree of any ω-rational language can therefore be computed...

A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : Part I

Jérémie Cabessa, Jacques Duparc (2009)

RAIRO - Theoretical Informatics and Applications

The algebraic study of formal languages shows that ω-rational sets correspond precisely to the ω-languages recognizable by finite ω-semigroups. Within this framework, we provide a construction of the algebraic counterpart of the Wagner hierarchy. We adopt a hierarchical game approach, by translating the Wadge theory from the ω-rational language to the ω-semigroup context. More precisely, we first show that the Wagner degree is indeed a syntactic invariant. We then define a reduction relation on...

A Hierarchy of Automatic ω-Words having a Decidable MSO Theory

Vince Bárány (2008)

RAIRO - Theoretical Informatics and Applications

We investigate automatic presentations of ω-words. Starting points of our study are the works of Rigo and Maes, Caucal, and Carton and Thomas concerning lexicographic presentation, MSO-interpretability in algebraic trees, and the decidability of the MSO theory of morphic words. Refining their techniques we observe that the lexicographic presentation of a (morphic) word is in a certain sense canonical. We then generalize our techniques to a hierarchy of classes of ω-words enjoying the above...

Algebra grammars

Radim Bělohlávek (1995)

Acta Mathematica et Informatica Universitatis Ostraviensis

Automata, Borel functions and real numbers in Pisot base

Benoit Cagnard, Pierre Simonnet (2007)

RAIRO - Theoretical Informatics and Applications

This note is about functions ƒ : Aω → Bω whose graph is recognized by a Büchi finite automaton on the product alphabet A x B. These functions are Baire class 2 in the Baire hierarchy of Borel functions and it is decidable whether such function are continuous or not. In 1920 W. Sierpinski showed that a function f : ℝ → ℝ is Baire class 1 if and only if both the overgraph and the undergraph of f are Fσ. We show that such characterization is also true for functions on infinite words if we replace the real...

Automata-based representations for infinite graphs

Salvatore La Torre, Margherita Napoli (2001)

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

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 its suffix and the last...

Automata-based Representations for Infinite Graphs

Salvatore La Torre, Margherita Napoli (2010)

RAIRO - Theoretical Informatics and Applications

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 its suffix and...

Currently displaying 1 – 15 of 15

Page 1