The state complexity of random DFAs

被引：1

作者：

Berend, Daniel ^{[1
]}

Kontorovich, Aryeh ^{[1
]}

机构：

[1] Ben Gurion Univ Negev, Beer Sheva, Israel

来源：

THEORETICAL COMPUTER SCIENCE | 2016年 / 652卷

基金：

以色列科学基金会;

关键词：

Random; Deterministic finite-state automaton; DFA; Minimal; RANDOM GENERATION;

D O I：

10.1016/j.tcs.2016.09.012

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The state complexity of a Deterministic Finite-state automaton (DFA) is the number of states in its minimal equivalent DFA. We study the state complexity of random n-state DFAs over a k-symbol alphabet, drawn uniformly from the set [n]([n]x[k]) x 2([n]) of all such automata. We show that, with high probability, the latter is alpha(k)n + O (root nlogn) for a certain explicit constant alpha(k). (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：102 / 108

页数：7

共 17 条

[1]

Angluin D, 2010, LECT NOTES ARTIF INT, V6331, P194, DOI 10.1007/978-3-642-16108-7_18

[2]

[Anonymous], INTRO AUTOMATA THEOR

[3]

[Anonymous], MATH NOTES ACAD SCI

[4]

Balle B., 2013, ARXIV13116830

[5] Enumeration and random generation of accessible automata [J].

Bassino, Frederique ;

Nicaud, Cyril .

THEORETICAL COMPUTER SCIENCE, 2007, 381 (1-3) :86-104

[6]

Bassino Frederique, 2012, STACS, P88

[7] Random generation of DFAs [J].

Champarnaud, JM ;

Paranthoën, T .

THEORETICAL COMPUTER SCIENCE, 2005, 330 (02) :221-235

[8]

Corless R. M., 1997, P 1997 INT S SYMB AL, P197, DOI DOI 10.1145/258726.258783

[9]

Domaratzki M., 2002, Journal of Automata, Languages and Combinatorics, V7, P469

[10]

Dubhashi D, 1998, RANDOM STRUCT ALGOR, V13, P99, DOI 10.1002/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO

← 1 2 →