Affordable Access

Publisher Website

A maxmin problem on finite automata

Authors
Journal
Discrete Applied Mathematics
0166-218X
Publisher
Elsevier
Publication Date
Volume
23
Issue
1
Identifiers
DOI: 10.1016/0166-218x(89)90037-1

Abstract

Abstract We solve the following problem proposed by Straubing. Given a two-letter alphabet A, what is the maximal number of states f( n) of the minimal automaton of a subset of A n , the set of all words of length n. We give an explicit formula to compute f( n) and we show that 1= lim inf n→∞nƒ(n)/2 n≤lim sup n→∞nƒ(n)/2 n=2 .

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

An intersection problem for finite automata

on Discrete Applied Mathematics Jan 01, 1988

A note on the emptiness problem for alternating fi...

on Theoretical Computer Science Mar 20, 2014

Intractability of decision problems for finite-mem...

on Theoretical Computer Science Jan 01, 2000
More articles like this..