Displaying similar documents to “k-counting automata”

k-counting automata

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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et 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 that it is decidable and give formal reasons why we believe...

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.

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...

On biautomata

Ondřej Klíma, Libor Polák (2012)

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

Similarity:

We initiate the theory and applications of biautomata. A biautomaton can read a word alternately from the left and from the right. We assign to each regular language its canonical biautomaton. This structure plays, among all biautomata recognizing the language , the same role as the minimal deterministic automaton has among all deterministic automata recognizing the language . We expect that from the graph structure of this automaton one could decide the membership of a given language...

Domain mu-calculus

Guo-Qiang Zhang (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The basic framework of domain -calculus was formulated in [39] more than ten years ago. This paper provides an improved formulation of a fragment of the -calculus without function space or powerdomain constructions, and studies some open problems related to this -calculus such as decidability and expressive power. A class of language equations is introduced for encoding -formulas in order to derive results related to decidability and expressive power of non-trivial fragments of the...

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...