6533b7d3fe1ef96bd1260802

RESEARCH PRODUCT

Descriptional and Computational Complexity of the Circuit Representation of Finite Automata

Māris Valdats

subject

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESFinite-state machineTheoretical computer scienceComputational complexity theoryComputer science020208 electrical & electronic engineering020206 networking & telecommunications02 engineering and technologyUpper and lower boundsAutomatonNondeterministic algorithmTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESSimple (abstract algebra)0202 electrical engineering electronic engineering information engineeringState (computer science)Representation (mathematics)Computer Science::Formal Languages and Automata Theory

description

In this paper we continue to investigate the complexity of the circuit representation of DFA—BC-complexity. We compare it with nondeterministic state complexity, obtain upper and lower bounds which differ only by a factor of 4 for a Binary input alphabet. Also we prove that many simple operations (determining if a state is reachable or if an automaton is minimal) are PSPACE-complete for DFA given in circuit representation.

yearjournalcountryeditionlanguage
2018-01-01
https://doi.org/10.1007/978-3-319-77313-1_8