State-complexity of finite-state devices, state compressibility and incompressibility

Research output: Contribution to journalArticlepeer-review

52 Scopus citations

Abstract

We study how the number of states may change when we convert between different finite-state devices. The devices that we consider are finite automata that are one-way or two-way, deterministic or nondeterministic or alternating. We obtain several new simulation results (e.g., an n-state 2NFA can be simulated by a 1NFA with ≤ 8n + 2 states, and by a 1AFA with ≤n2 states), and state-incompressibility results (e.g., in order to simulate an n-state 2DFA, a 1NFA needs ≥√/2n-2 states, and a 2AFA needs ≥c√n states for some constant c, in general).

Original languageEnglish (US)
Pages (from-to)237-269
Number of pages33
JournalMathematical Systems Theory
Volume26
Issue number3
DOIs
StatePublished - Sep 1 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'State-complexity of finite-state devices, state compressibility and incompressibility'. Together they form a unique fingerprint.

Cite this