Concepedia

State Complexity

State Complexity is the minimum number of states required by a deterministic finite automaton to recognize a given regular language, serving as a measure of the inherent structural complexity of the language within the theory of finite automata.

250

Publications

12K

Citations

357

Authors

236

Institutions

Publications per year

2017–2026

35

Parents

Publications

250

Complexity of automaton identification from given data

Eric Gold · Information and Control · 1978 · 770 citations

, , +12

Altered resting state complexity in schizophrenia

Danielle S. Bassett, Brent Nelson, Bryon A. Mueller et al. · NeuroImage · 2011 · 431 citations

, , +12

Toward a Definition of Complexity for Quantum Field Theory States

Shira Chapman, Michał P. Heller, Hugo Marrochio et al. · Physical Review Letters · 2018 · 423 citations · Full text

, , +16

The state complexities of some basic operations on regular languages

Sheng Yü, Qingyu Zhuang, Kai Salomaa · Theoretical Computer Science · 1994 · 349 citations

, , +12

Decoding of trellis-encoded signals in the presence of intersymbol interference and noise

P. Chevillat, Evangelos Eleftheriou · IEEE Transactions on Communications · 1989 · 242 citations

, , +17

1–5 of 250

Authors

357

  1. SY
    Sheng Yü

    Western University, Canada

    20 publications · 1.3K citations

    18

    h-index

  2. KS
    Kai Salomaa

    Queen's University, Canada

    26 publications · 1.1K citations

    16

    h-index

  3. GJ
    Galina Jirásková

    Slovak Academy of Sciences, Slovakia

    14 publications · 433 citations

    12

    h-index

  4. AO
    Alexander Okhotin

    University of Turku, Finland

    8 publications · 221 citations

    8

    h-index

  5. MD
    Michael Domaratzki

    University of Manitoba, Canada

    8 publications · 194 citations

    8

    h-index

1–5 of 357

Institutions

236

  1. Western University

    London, Canada

    17 h-index

    39 publications

    1.9K citations

  2. Queen's University

    Kingston, Canada

    16 h-index

    31 publications

    924 citations

  3. University of Waterloo

    Waterloo, Canada

    12 h-index

    25 publications

    1.2K citations

  4. Slovak Academy of Sciences

    Bratislava, Slovakia

    12 h-index

    12 publications

    408 citations

  5. Mathematical Institute of the Slovak Academy of Sciences

    Bratislava, Slovakia

    11 h-index

    11 publications

    392 citations

  6. University of Turku

    Turku, Finland

    8 h-index

    8 publications

    558 citations

  7. Centre National de la Recherche Scientifique

    Paris, France

    5 h-index

    7 publications

    105 citations

  8. Justus-Liebig-Universität Gießen

    Giessen, Germany

    5 h-index

    10 publications

    484 citations

1–8 of 236

Venues

  1. Theoretical Computer Science

    28 publications · 1.5K citations

    19

    h-index

  2. International Journal of Foundations of Computer Science

    IJFCS · 22 publications · 813 citations

    16

    h-index

  3. IEEE Transactions on Information Theory

    12 publications · 759 citations

    12

    h-index

  4. Fundamenta Informaticae

    10 publications · 263 citations

    10

    h-index

  5. Justus-Liebig-Universität Gießen

    Repository · 7 publications · 204 citations

    7

    h-index

1–5