International Journal of Foundations of Computer Science · 2019 · 12 citations · 7 references
ComputingComputer ScienceMathematicsAlgorithmsTheory Of ComputationAutomata TheoryComputational ComplexityFinite AutomataFinite-state MachinesFormal LanguagesStructural ComplexityAutomata-theoretic CharacterizationsComplexityComputational Complexity Of LanguagesFinite Automata TheoryState Complexity
We prove PSPACE-completeness of checking whether a given ideal language serves as the language of reset words for some automaton with at most four states over a binary alphabet. We compare the reset complexity and the state complexity for languages related to slowly synchronizing automata.
7
Word problems requiring exponential time(Preliminary Report)
Larry J. Stockmeyer, Albert R. Meyer · 1973 · 874 citations
Lower bounds for natural proof systems
Dexter Kozen · 1977 · 446 citations