6533b82bfe1ef96bd128d58f

RESEARCH PRODUCT

Multiple Usage of Random Bits in Finite Automata

Rūsiņš Freivalds

subject

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESNested wordFinite-state machineTheoretical computer scienceKolmogorov complexityComputer scienceω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesBit fieldTuring machinesymbols.namesakeTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESsymbolsQuantum finite automataAutomata theoryArithmeticComputer Science::DatabasesComputer Science::Formal Languages and Automata Theory

description

Finite automata with random bits written on a separate 2-way readable tape can recognize languages not recognizable by probabilistic finite automata. This shows that repeated reading of random bits by finite automata can have big advantages over one-time reading of random bits.

yearjournalcountryeditionlanguage
2012-01-01
https://doi.org/10.1007/978-3-642-29952-0_50