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

Previous Page 2 Next

Displaying 21 – 40 of 305

Showing per page

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 ambiguity in DOS systems

Andrzej Ehrenfeucht, David Haussler, Grzegorz Rozenberg (1984)

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

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 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 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 characteristic formulae for Event-Recording Automata

Omer Landry Nguena Timo, Pierre-Alain Reynier (2013)

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

A standard bridge between automata theory and logic is provided by the notion of characteristic formula. This paper investigates this problem for the class of event-recording automata (ERA), a subclass of timed automata in which clocks are associated with actions and that enjoys very good closure properties. We first study the problem of expressing characteristic formulae for ERA in Event-Recording Logic (ERL ), a logic introduced by Sorea to express event-based timed specifications. We prove that...

On coalgebras and type transformations

H. Peter Gumm (2007)

Discussiones Mathematicae - General Algebra and Applications

We show that for an arbitrary Set-endofunctor T the generalized membership function given by a sub-cartesian transformation μ from T to the filter functor 𝔽 can be alternatively defined by the collection of subcoalgebras of constant T-coalgebras. Sub-natural transformations ε between any two functors S and T are shown to be sub-cartesian if and only if they respect μ. The class of T-coalgebras whose structure map factors through ε is shown to be a covariety if ε is a natural and sub-cartesian mono-transformation....

Currently displaying 21 – 40 of 305