Probabilism versus Alternation for Automata
From MaRDI portal
Publication:6163621
DOI10.1007/978-3-319-98355-4_8zbMath1514.68111MaRDI QIDQ6163621
Publication date: 30 June 2023
Published in: Adventures Between Lower Bounds and Higher Altitudes (Search for Journal in Brave)
Related Items (1)
Cites Work
- An alternating hierarchy for finite automata
- Ambiguity and communication
- BPP and the polynomial hierarchy
- A comparison of two lower-bound methods for communication complexity
- More on BPP and the polynomial-time hierarchy
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Communication complexity method for measuring nondeterminism in finite automata
- On multi-partition communication complexity
- On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
- Comparing the size of NFAs with and without \(\epsilon\)-transitions
- Size Complexity of Two-Way Finite Automata
- Finite monoids and the fine structure of NC 1
- Alternation
- Nondeterministic Communication with a Limited Number of Advice Bits
This page was built for publication: Probabilism versus Alternation for Automata
