A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
From MaRDI portal
Publication:3495661
DOI10.1137/0219069zbMath0711.68075OpenAlexW1987322712WikidataQ59595164 ScholiaQ59595164MaRDI QIDQ3495661
Cynthia Dwork, Larry J. Stockmeyer
Publication date: 1990
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/f4157a37ad43afc8f9d88a37e5e6e1ef63a8a8d9
complexity theoryprobabilistic automatafinite-state automatonnondeterministic finite-state automatonnonregular language
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Two-way and one-way quantum and classical automata with advice for online minimization problems, Infinite vs. finite size-bounded randomized computations, Affine automata verifiers, Uncountable realtime probabilistic classes, On some variations of two-way probabilistic finite automata models, Quantum Finite Automata: A Modern Introduction, State succinctness of two-way finite automata with quantum and classical states, On languages accepted with simultaneous complexity bounds and their ranking problem, Automaticity. II: Descriptional complexity in the unary case, Reducing Acyclic Cover Transducers, Learning finite cover automata from queries, Size complexity of rotating and sweeping automata, Lifting query complexity to time-space complexity for two-way finite automata, Modeling of RNA secondary structures using two-way quantum finite automata, COUNTING THE NUMBER OF MINIMAL DFCA OBTAINED BY MERGING STATES, COVER TRANSDUCERS FOR FUNCTIONS WITH FINITE DOMAIN, QUANTUM COUNTER AUTOMATA, SOME LANGUAGES RECOGNIZED BY TWO-WAY FINITE AUTOMATA WITH QUANTUM AND CLASSICAL STATES, Automaticity. IV: Sequences, sets, and diversity, A note on two-way probabilistic automata, New size hierarchies for two way automata, AN EFFICIENT ALGORITHM FOR CONSTRUCTING MINIMAL COVER AUTOMATA FOR FINITE LANGUAGES, Similarity relations and cover automata, Probabilistic Acceptors for Languages over Infinite Words, Minimal cover-automata for finite languages, Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice, New Results on the Minimum Amount of Useful Space, Uncountable classical and quantum complexity classes, Size Complexity of Two-Way Finite Automata, Theory of one-tape linear-time Turing machines, CLOSURE PROPERTY OF PROBABILISTIC TURING MACHINES AND ALTERNATING TURING MACHINES WITH SUBLOGARITHMIC SPACES, Two-way finite automata with quantum and classical states., Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata, Computation with multiple CTCs of fixed length and width
