Search results

Sort By:

Limit search:

Experiments on Synchronizing Automata

100%

Roman A.

Schedae Informaticae

2010

vol. 19

This work is motivated by the ˇCern´y Conjecture – an old unsolved problem in the automata theory. We describe the results of the experiments on synchronizing automata, which have led us to two interesting results. The first one is that the size of an automaton alphabet may play an important role in the issue of synchronization: we have found a 5-state automaton over a 3-letter alphabet which attains the upper bound from the ˇCern´y Conjecture, while there is no such automaton (except ˇCern´y automaton C5) over a binary alphabet. The second result emerging from the experiments is a theorem describing the dependencies between the automaton structure S expressed in terms of the so-called merging system and the maximal length of all minimal synchronizing words for automata of type S.

On the number of clusterings in a hierarchical classication model with overlapping clusters

51%

Roman A., Podolak I. T., Deszyńska A.

Schedae Informaticae

2011

vol. 20

This paper shows a new combinatorial problem which emerged from studies on an artificial intelligence classification model of a hierarchical classifier. We introduce the notion of proper clustering and show how to count their number in a special case when 3 clusters are allowed. An algorithm that generates all clusterings is given. We also show that the proposed approach can be generalized to any number of clusters, and can be automatized. Finally, we show the relationship between the problem of counting clusterings and the Dedekind problem.

Refine search results

2 Schedae Informaticae

1 2011

1 2010

2 Roman A.

1 Deszyńska A.

1 Podolak I. T.

Search results

Experiments on Synchronizing Automata

On the number of clusterings in a hierarchical classication model with overlapping clusters