The Experts below are selected from a list of 324 Experts worldwide ranked by ideXlab platform
Maria Madonia - One of the best experts on this subject based on the ideXlab platform.
-
Deterministic and unambiguous two-dimensional languages over one-Letter Alphabet
Theoretical Computer Science, 2009Co-Authors: Marcella Anselmo, Maria MadoniaAbstract:The paper focuses on deterministic and unambiguous recognizable two-dimensional languages with particular attention to the case of a one-Letter Alphabet. The family DREC(1) of deterministic languages over a one-Letter Alphabet is characterized as both L(DOTA)(1), the class of languages accepted by deterministic on-line tessellation acceptors, and L(2AFA)(1), the class of languages recognized by 2-way alternating finite automata. We show that there are inherently ambiguous languages and unambiguously recognizable languages that cannot be deterministically recognized even in the case of a one-Letter Alphabet. In particular we show that on-line tessellation acceptors are more powerful than their deterministic counterpart, even in the case of a one-Letter Alphabet. Finally we show that DREC(1) is complex enough not to be characterized in terms of classical operations.
-
deterministic two dimensional languages over one Letter Alphabet
Conference on Algebraic Informatics, 2007Co-Authors: Marcella Anselmo, Maria MadoniaAbstract:We study the family DREC(1) of deterministic tiling recognizable two-dimensional languages in the case of a one-Letter Alphabet. The family coincides with both the class of languages accepted by deterministic on-line tessellation acceptors (L(DOTA)(1)) and the one of languages recognized by 2-way alternating finite automata (L(2AFA)(1)). We show that DREC(1) is complex enough to contain languages that cannot be realized by classical operations, while other languages constructed using classical operations cannot be deterministically recognized. Furthermore we prove that there are unambiguously recognizable languages that cannot be deterministically recognized even in the case of one-Letter Alphabet. In particular L(DOTA)(1) is different from L(OTA)(1) (its non-deterministic counterpart).
-
New operations and regular expressions for two-dimensional languages over one-Letter Alphabet
Theoretical Computer Science, 2005Co-Authors: Marcella Anselmo, Dora Giammarresi, Maria MadoniaAbstract:We consider the problem of defining regular expressions to characterize the class of recognizable picture languages in the case of a one-Letter Alphabet. We define a diagonal concatenation and its star and consider two different families, L(D) and L(CRD), of languages denoted by regular expressions involving such operations plus classical operations. L(D) is characterized both in terms of rational relations and in terms of two-dimensional automata moving only right and down. L(CRD) is included in REC and contains languages defined by three-way automata while languages in L(CRD) necessarily satisfy some regularity conditions. Finally, we introduce new definitions of advanced stars expressing the necessity of conceptually different definitions for iteration.
-
Developments in Language Theory - Regular expressions for two-dimensional languages over one-Letter Alphabet
Developments in Language Theory, 2004Co-Authors: Marcella Anselmo, Dora Giammarresi, Maria MadoniaAbstract:The aim of this paper is to give regular expressions for two-dimensional picture languages. The paper focuses on a one-Letter Alphabet case, that corresponds to the study of “shapes” of families of pictures. A new diagonal concatenation operation is defined. Languages denoted by regular expressions with union, diagonal concatenation and its closure are characterized both in terms of rational relations and in terms of two-dimensional automata moving only right and down. The class of languages denoted by regular expressions with union, column, row and diagonal concatenation, and their closures are included in REC and strictly contains languages defined by three-way automata, but they are not comparable with ones defined by four-way automata. In order to encompass a wider class of languages, we propose some new operations that define languages that still lie in REC.
-
Developments in Language Theory - Regular expressions for two-dimensional languages over one-Letter Alphabet
Developments in Language Theory, 2004Co-Authors: Marcella Anselmo, Dora Giammarresi, Maria MadoniaAbstract:The aim of this paper is to give regular expressions for two-dimensional picture languages. The paper focuses on a one-Letter Alphabet case, that corresponds to the study of “shapes” of families of pictures. A new diagonal concatenation operation is defined. Languages denoted by regular expressions with union, diagonal concatenation and its closure are characterized both in terms of rational relations and in terms of two-dimensional automata moving only right and down. The class of languages denoted by regular expressions with union, column, row and diagonal concatenation, and their closures are included in REC and strictly contains languages defined by three-way automata, but they are not comparable with ones defined by four-way automata. In order to encompass a wider class of languages, we propose some new operations that define languages that still lie in REC.
Ines Klimann - One of the best experts on this subject based on the ideXlab platform.
-
On the supports of recognizable series over a field and a single Letter Alphabet
Information Processing Letters, 2011Co-Authors: Guillaume Chapuy, Ines KlimannAbstract:We prove that the support of a recognizable series over a field of characteristic zero and a single Letter Alphabet is recognizable. This provides an answer to a question of Kirsten (2009) [4]. Then we give an example of a recognizable series over a field of prime characteristic and a single Letter Alphabet whose support is not recognizable which provides an answer to a question of Kirsten and Quaas (2011) [5].
-
On the supports of recognizable series over a field and a single Letter Alphabet
Information Processing Letters, 2011Co-Authors: Guillaume Chapuy, Ines KlimannAbstract:International audienceWe prove that the support of a recognizable series over a field of characteristic zero and a single Letter Alphabet is recognizable. This provides an answer to a question of Kirsten (2009). Then we give an example of a recognizable series over a field of prime characteristic and a single Letter Alphabet whose support is not recognizable which provides an answer to a question of Kirsten and Quaas (2011)
Marcella Anselmo - One of the best experts on this subject based on the ideXlab platform.
-
Deterministic and unambiguous two-dimensional languages over one-Letter Alphabet
Theoretical Computer Science, 2009Co-Authors: Marcella Anselmo, Maria MadoniaAbstract:The paper focuses on deterministic and unambiguous recognizable two-dimensional languages with particular attention to the case of a one-Letter Alphabet. The family DREC(1) of deterministic languages over a one-Letter Alphabet is characterized as both L(DOTA)(1), the class of languages accepted by deterministic on-line tessellation acceptors, and L(2AFA)(1), the class of languages recognized by 2-way alternating finite automata. We show that there are inherently ambiguous languages and unambiguously recognizable languages that cannot be deterministically recognized even in the case of a one-Letter Alphabet. In particular we show that on-line tessellation acceptors are more powerful than their deterministic counterpart, even in the case of a one-Letter Alphabet. Finally we show that DREC(1) is complex enough not to be characterized in terms of classical operations.
-
deterministic two dimensional languages over one Letter Alphabet
Conference on Algebraic Informatics, 2007Co-Authors: Marcella Anselmo, Maria MadoniaAbstract:We study the family DREC(1) of deterministic tiling recognizable two-dimensional languages in the case of a one-Letter Alphabet. The family coincides with both the class of languages accepted by deterministic on-line tessellation acceptors (L(DOTA)(1)) and the one of languages recognized by 2-way alternating finite automata (L(2AFA)(1)). We show that DREC(1) is complex enough to contain languages that cannot be realized by classical operations, while other languages constructed using classical operations cannot be deterministically recognized. Furthermore we prove that there are unambiguously recognizable languages that cannot be deterministically recognized even in the case of one-Letter Alphabet. In particular L(DOTA)(1) is different from L(OTA)(1) (its non-deterministic counterpart).
-
New operations and regular expressions for two-dimensional languages over one-Letter Alphabet
Theoretical Computer Science, 2005Co-Authors: Marcella Anselmo, Dora Giammarresi, Maria MadoniaAbstract:We consider the problem of defining regular expressions to characterize the class of recognizable picture languages in the case of a one-Letter Alphabet. We define a diagonal concatenation and its star and consider two different families, L(D) and L(CRD), of languages denoted by regular expressions involving such operations plus classical operations. L(D) is characterized both in terms of rational relations and in terms of two-dimensional automata moving only right and down. L(CRD) is included in REC and contains languages defined by three-way automata while languages in L(CRD) necessarily satisfy some regularity conditions. Finally, we introduce new definitions of advanced stars expressing the necessity of conceptually different definitions for iteration.
-
Developments in Language Theory - Regular expressions for two-dimensional languages over one-Letter Alphabet
Developments in Language Theory, 2004Co-Authors: Marcella Anselmo, Dora Giammarresi, Maria MadoniaAbstract:The aim of this paper is to give regular expressions for two-dimensional picture languages. The paper focuses on a one-Letter Alphabet case, that corresponds to the study of “shapes” of families of pictures. A new diagonal concatenation operation is defined. Languages denoted by regular expressions with union, diagonal concatenation and its closure are characterized both in terms of rational relations and in terms of two-dimensional automata moving only right and down. The class of languages denoted by regular expressions with union, column, row and diagonal concatenation, and their closures are included in REC and strictly contains languages defined by three-way automata, but they are not comparable with ones defined by four-way automata. In order to encompass a wider class of languages, we propose some new operations that define languages that still lie in REC.
-
Developments in Language Theory - Regular expressions for two-dimensional languages over one-Letter Alphabet
Developments in Language Theory, 2004Co-Authors: Marcella Anselmo, Dora Giammarresi, Maria MadoniaAbstract:The aim of this paper is to give regular expressions for two-dimensional picture languages. The paper focuses on a one-Letter Alphabet case, that corresponds to the study of “shapes” of families of pictures. A new diagonal concatenation operation is defined. Languages denoted by regular expressions with union, diagonal concatenation and its closure are characterized both in terms of rational relations and in terms of two-dimensional automata moving only right and down. The class of languages denoted by regular expressions with union, column, row and diagonal concatenation, and their closures are included in REC and strictly contains languages defined by three-way automata, but they are not comparable with ones defined by four-way automata. In order to encompass a wider class of languages, we propose some new operations that define languages that still lie in REC.
Jacques Sakarovitch - One of the best experts on this subject based on the ideXlab platform.
-
one sided dyck reduction over two Letter Alphabet and deterministic context free languages
Mathematical Foundations of Computer Science, 1996Co-Authors: Fabienne Romanian, Jacques SakarovitchAbstract:We characterize the deterministic context-free languages that are unions of equivalence classes in the equivalence generated by the one-sided Dyck reduction over a two-Letter Alphabet.
-
MFCS - One-sided Dyck reduction over two Letter Alphabet and deterministic context-free languages
Lecture Notes in Computer Science, 1Co-Authors: Fabienne Romanian, Jacques SakarovitchAbstract:We characterize the deterministic context-free languages that are unions of equivalence classes in the equivalence generated by the one-sided Dyck reduction over a two-Letter Alphabet.
Dora Giammarresi - One of the best experts on this subject based on the ideXlab platform.
-
New operations and regular expressions for two-dimensional languages over one-Letter Alphabet
Theoretical Computer Science, 2005Co-Authors: Marcella Anselmo, Dora Giammarresi, Maria MadoniaAbstract:We consider the problem of defining regular expressions to characterize the class of recognizable picture languages in the case of a one-Letter Alphabet. We define a diagonal concatenation and its star and consider two different families, L(D) and L(CRD), of languages denoted by regular expressions involving such operations plus classical operations. L(D) is characterized both in terms of rational relations and in terms of two-dimensional automata moving only right and down. L(CRD) is included in REC and contains languages defined by three-way automata while languages in L(CRD) necessarily satisfy some regularity conditions. Finally, we introduce new definitions of advanced stars expressing the necessity of conceptually different definitions for iteration.
-
Developments in Language Theory - Regular expressions for two-dimensional languages over one-Letter Alphabet
Developments in Language Theory, 2004Co-Authors: Marcella Anselmo, Dora Giammarresi, Maria MadoniaAbstract:The aim of this paper is to give regular expressions for two-dimensional picture languages. The paper focuses on a one-Letter Alphabet case, that corresponds to the study of “shapes” of families of pictures. A new diagonal concatenation operation is defined. Languages denoted by regular expressions with union, diagonal concatenation and its closure are characterized both in terms of rational relations and in terms of two-dimensional automata moving only right and down. The class of languages denoted by regular expressions with union, column, row and diagonal concatenation, and their closures are included in REC and strictly contains languages defined by three-way automata, but they are not comparable with ones defined by four-way automata. In order to encompass a wider class of languages, we propose some new operations that define languages that still lie in REC.
-
Developments in Language Theory - Regular expressions for two-dimensional languages over one-Letter Alphabet
Developments in Language Theory, 2004Co-Authors: Marcella Anselmo, Dora Giammarresi, Maria MadoniaAbstract:The aim of this paper is to give regular expressions for two-dimensional picture languages. The paper focuses on a one-Letter Alphabet case, that corresponds to the study of “shapes” of families of pictures. A new diagonal concatenation operation is defined. Languages denoted by regular expressions with union, diagonal concatenation and its closure are characterized both in terms of rational relations and in terms of two-dimensional automata moving only right and down. The class of languages denoted by regular expressions with union, column, row and diagonal concatenation, and their closures are included in REC and strictly contains languages defined by three-way automata, but they are not comparable with ones defined by four-way automata. In order to encompass a wider class of languages, we propose some new operations that define languages that still lie in REC.
-
Regular expressions for two-dimensional languages over one-Letter Alphabet
Lecture Notes in Computer Science, 2004Co-Authors: Marcella Anselmo, Dora Giammarresi, Maria MadoniaAbstract:The aim of this paper is to give regular expressions for two-dimensional picture languages. The paper focuses on a one-Letter Alphabet case, that corresponds to the study of "shapes" of families of pictures. A new diagonal concatenation operation is defined. Languages denoted by regular expressions with union, diagonal concatenation and its closure are characterized both in terms of rational relations and in terms of two-dimensional automata moving only right and down. The class of languages denoted by regular expressions with union: column, row and diagonal concatenation, and their closures are included in REC and strictly contains languages defined by three-way automata, but they are not comparable with ones defined by four-way automata. In order to encompass a wider class of languages, we propose some new operations that define languages that still lie in REC.