A4 Vertaisarvioitu artikkeli konferenssijulkaisussa

Words of Minimum Rank in Deterministic Finite Automata




TekijätJarkko Kari, Andrew Ryzhikov, Anton Varonka

ToimittajaHofman P., Skrzypczak M.

Konferenssin vakiintunut nimiInternational Conference on Developments in Language Theory

Julkaisuvuosi2019

JournalLecture Notes in Computer Science

Kokoomateoksen nimiDevelopments in Language Theory 23rd International Conference, DLT 2019, Warsaw, Poland, August 5–9, 2019, Proceedings

Sarjan nimiTheoretical Computer Science and General Issues

Numero sarjassa11647

Aloitussivu74

Lopetussivu87

ISBN978-3-030-24885-7

DOIhttps://doi.org/10.1007/978-3-030-24886-4_5

Rinnakkaistallenteen osoitehttps://research.utu.fi/converis/portal/detail/Publication/43959793


Tiivistelmä

The rank of a word in a deterministic finite automaton is the size of the image of the whole state set under the mapping defined by this word. We study the length of shortest words of minimum rank in several classes of complete deterministic finite automata, namely, strongly connected and Eulerian automata. A conjecture bounding this length is known as the Rank Conjecture, a generalization of the well known Černý Conjecture. We prove upper bounds on the length of shortest words of minimum rank in automata from the mentioned classes, and provide several families of automata with long words of minimum rank. Some results in this direction are also obtained for automata with rank equal to period (the greatest common divisor of lengths of all cycles) and for circular automata.


Ladattava julkaisu

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





Last updated on 2024-26-11 at 14:13