pith. machine review for the scientific record. sign in

arxiv: 0711.4990 · v1 · submitted 2007-11-30 · 💻 cs.DM · cs.DS

Recognition: unknown

Finding the growth rate of a regular language in polynomial time

Dalia Krieger , Narad Rampersad , Jeffrey Shallit
Authors on Pith no claims yet
classification 💻 cs.DM cs.DS
keywords growthpolynomiallanguagetimedetermineacceptingacceptsalgorithm
0
0 comments X
read the original abstract

We give an O(n^3+n^2 t) time algorithm to determine whether an NFA with n states and t transitions accepts a language of polynomial or exponential growth. We also show that given a DFA accepting a language of polynomial growth, we can determine the order of polynomial growth in quadratic time.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Asymptotic Hausdorff and Language Similarity

    cs.FL 2026-05 unverdicted novelty 6.0

    Asymptotic Hausdorff lifting defines asymptotic similarity metrics on languages under normalized edit distances and characterizes the induced equivalence classes on regular languages.