0000000000659152

AUTHOR

Uğur Küçük

showing 2 related works from this author

Finite Automata with Advice Tapes

2013

We define a model of advised computation by finite automata where the advice is provided on a separate tape. We consider several variants of the model where the advice is deterministic or randomized, the input tape head is allowed real-time, one-way, or two-way access, and the automaton is classical or quantum. We prove several separation results among these variants, and establish the relationships between this model and the previously studied ways of providing advice to finite automata.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESbusiness.product_categoryTheoretical computer scienceFinite-state machineComputer scienceTape headω-automatonDeterministic finite automatonDeterministic automatonTwo-way deterministic finite automatonNondeterministic finite automatonbusinessAdvice (complexity)Computer Science::Formal Languages and Automata Theory
researchProduct

FINITE AUTOMATA WITH ADVICE TAPES

2014

We define a model of advised computation by finite automata where the advice is provided on a separate tape. We consider several variants of the model where the advice is deterministic or randomized, the input tape head is allowed real-time, one-way, or two-way access, and the automaton is classical or quantum. We prove several separation results among these variants, demonstrate an infinite hierarchy of language classes recognized by automata with increasing advice lengths, and establish the relationships between this and the previously studied ways of providing advice to finite automata.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoretical computer scienceComputer scienceω-automatonTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonDeterministic automatonComputer Science (miscellaneous)Automata theoryQuantum finite automataTwo-way deterministic finite automatonNondeterministic finite automatonAdvice (complexity)AlgorithmComputer Science::Formal Languages and Automata TheoryInternational Journal of Foundations of Computer Science
researchProduct