Displaying similar documents to “Wadge Degrees of ω-Languages of Deterministic Turing Machines”

-counting automata

Joël Allred, Ulrich Ultes-Nitsche (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper, we define -counting automata as recognizers for -languages, languages of infinite words. We prove that the class of -languages they recognize is a proper extension of the -regular languages. In addition we prove that languages recognized by -counting automata are closed under Boolean operations. It remains an open problem whether or not emptiness is decidable for -counting automata. However, we conjecture strongly...

A Space Lower Bound for Acceptance by One-Way Π-Alternating Machines

Viliam Geffert, Norbert Popély (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We show that one-way Π-alternating Turing machines cannot accept unary nonregular languages in (log ) space. This holds for an mode of space complexity measure, defined as the worst cost of any accepting computation. This lower bound should be compared with the corresponding bound for one-way Σ-alternating machines, that are able to accept unary nonregular languages in space (log log ). Thus, Σ-alternation is more powerful than Π-alternation for space bounded one-way machines with...

Idealized coinductive type systems for imperative object-oriented programs

Davide Ancona, Giovanni Lagorio (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

In recent work we have proposed a novel approach to define idealized type systems for object-oriented languages, based on of programs into Horn formulas which are interpreted w.r.t. the coinductive (that is, the greatest) Herbrand model. In this paper we investigate how this approach can be applied also in the presence of imperative features. This is made possible by considering a natural translation of intermediate form programs into Horn formulas, where functions correspond to...

Circular splicing and regularity

Paola Bonizzoni, Clelia De Felice, Giancarlo Mauri, Rosalba Zizza (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

has been very recently introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with linear splicing. In this paper we restrict our study to the relationship between and languages generated by and provide some results towards a characterization of the intersection between these two classes. We consider the class of languages , called here , which are closed under conjugacy relation and with being a regular language. Using automata...

Multi-dimensional sets recognizable in all abstract numeration systems

Émilie Charlier, Anne Lacroix, Narad Rampersad (2012)

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

Similarity:

We prove that the subsets of that are -recognizable for all abstract numeration systems are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting.

Multi-dimensional sets recognizable in all abstract numeration systems

Émilie Charlier, Anne Lacroix, Narad Rampersad (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

We prove that the subsets of that are -recognizable for all abstract numeration systems are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting.

Idealized coinductive type systems for imperative object-oriented programs

Davide Ancona, Giovanni Lagorio (2011)

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

Similarity:

In recent work we have proposed a novel approach to define idealized type systems for object-oriented languages, based on of programs into Horn formulas which are interpreted w.r.t. the coinductive (that is, the greatest) Herbrand model. In this paper we investigate how this approach can be applied also in the presence of imperative features. This is made possible by considering a natural translation of intermediate form programs into Horn formulas, where functions correspond to union...