O jednom typu konečného automatu
Page 1 Next
Displaying 1 – 20 of 33
On a subclass of context-free groups
Thomas Herbst (1991)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
On abelian repetition threshold
Alexey V. Samsonov, Arseny M. Shur (2012)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
We study the avoidance of Abelian powers of words and consider three reasonable generalizations of the notion of Abelian power to fractional powers. Our main goal is to find an Abelian analogue of the repetition threshold, i.e., a numerical value separating k-avoidable and k-unavoidable Abelian powers for each size k of the alphabet. We prove lower bounds for the Abelian repetition threshold for large alphabets and all definitions of Abelian fractional power. We develop a method estimating the exponential...
On Abelian repetition threshold
Alexey V. Samsonov, Arseny M. Shur (2012)
RAIRO - Theoretical Informatics and Applications
We study the avoidance of Abelian powers of words and consider three reasonable generalizations of the notion of Abelian power to fractional powers. Our main goal is to find an Abelian analogue of the repetition threshold, i.e., a numerical value separating k-avoidable and k-unavoidable Abelian powers for each size k of the alphabet. We prove lower bounds for the Abelian repetition threshold for large alphabets and all definitions of Abelian fractional ...
On an algorithm to decide whether a free group is a free factor of another
Pedro V. Silva, Pascal Weil (2008)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
We revisit the problem of deciding whether a finitely generated subgroup is a free factor of a given free group . Known algorithms solve this problem in time polynomial in the sum of the lengths of the generators of and exponential in the rank of . We show that the latter dependency can be made exponential in the rank difference rank - rank, which often makes a significant change.
On an algorithm to decide whether a free group is a free factor of another
Pedro V. Silva, Pascal Weil (2007)
RAIRO - Theoretical Informatics and Applications
We revisit the problem of deciding whether a finitely generated subgroup H is a free factor of a given free group F. Known algorithms solve this problem in time polynomial in the sum of the lengths of the generators of H and exponential in the rank of F. We show that the latter dependency can be made exponential in the rank difference rank(F) - rank(H), which often makes a significant change.
On biautomata
Ondřej Klíma, Libor Polák (2012)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
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 L its canonical biautomaton. This structure plays, among all biautomata recognizing the language L, the same role as the minimal deterministic automaton has among all deterministic automata recognizing the language L. We expect that from the graph structure of this automaton one could decide the membership of a given language for certain...
On biautomata∗
Ondřej Klíma, Libor Polák (2012)
RAIRO - Theoretical Informatics and Applications
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 L its canonical biautomaton. This structure plays, among all biautomata recognizing the language L, the same role as the minimal deterministic automaton has among all deterministic automata recognizing the language L. We expect that from the graph structure of this automaton one could decide the membership of a given language for certain...
On commutative Kleene monoids.
C.P. Rupert (1991)
Semigroup forum
On conjugacy of languages
Julien Cassaigne, Juhani Karhumäki, Ján Maňuch (2001)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
We say that two languages and are conjugates if they satisfy the conjugacy equation for some language . We study several problems associated with this equation. For example, we characterize all sets which are conjugated a two-element biprefix set , as well as all two-element sets which are conjugates.
On Conjugacy of Languages
Julien Cassaigne, Juhani Karhumäki, Ján Maňuch (2010)
RAIRO - Theoretical Informatics and Applications
We say that two languages X and Y are conjugates if they satisfy the conjugacy equationXZ = ZY for some language Z. We study several problems associated with this equation. For example, we characterize all sets which are conjugated via a two-element biprefix set Z, as well as all two-element sets which are conjugates.
On graph products of automatic monoids
A. Veloso Da Costa (2001)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
The graph product is an operator mixing direct and free products. It is already known that free products and direct products of automatic monoids are automatic. The main aim of this paper is to prove that graph products of automatic monoids of finite geometric type are still automatic. A similar result for prefix-automatic monoids is established.
On graph products of automatic monoids
A. Veloso da Costa (2010)
RAIRO - Theoretical Informatics and Applications
The graph product is an operator mixing direct and free products. It is already known that free products and direct products of automatic monoids are automatic. The main aim of this paper is to prove that graph products of automatic monoids of finite geometric type are still automatic. A similar result for prefix-automatic monoids is established.
On limits in complete semirings.
G. Karner (1992)
Semigroup forum
On quasi-homomorphisms and compositions of automata
Cao Quyê't Thă'ng (1981)
Časopis pro pěstování matematiky
On right congruences associated with the input semigroup S of automata.
C.H. Park (1994)
Semigroup forum
On separating sets of words. I.
Václav Flaška, Tomáš Kepka, Juha Kortelainen (2008)
Acta Universitatis Carolinae. Mathematica et Physica
On separating sets of words. II.
Václav Flaška, Tomáš Kepka, Juha Kortelainen (2009)
Acta Universitatis Carolinae. Mathematica et Physica
On shuffle ideals
Pierre-Cyrille Héam (2002)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
A shuffle ideal is a language which is a finite union of languages of the form where is a finite alphabet and the ’s are letters. We show how to represent shuffle ideals by special automata and how to compute these representations. We also give a temporal logic characterization of shuffle ideals and we study its expressive power over infinite words. We characterize the complexity of deciding whether a language is a shuffle ideal and we give a new quadratic algorithm for this problem. Finally...
On Shuffle Ideals
Pierre-Cyrille Héam (2010)
RAIRO - Theoretical Informatics and Applications
A shuffle ideal is a language which is a finite union of languages of the form A*a1A*...A*ak where A is a finite alphabet and the ai's are letters. We show how to represent shuffle ideals by special automata and how to compute these representations. We also give a temporal logic characterization of shuffle ideals and we study its expressive power over infinite words. We characterize the complexity of deciding whether a language is a shuffle ideal and we give a new quadratic algorithm for...
Currently displaying 1 – 20 of 33
Page 1 Next