The search session has expired. Please query the service again.
Displaying 21 –
40 of
305
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...
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
...
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.
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.
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...
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...
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...
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