Complexity of multi-head finite automata: origins and directions
From MaRDI portal
(Redirected from Publication:616495)
Recommendations
- Multi-head finite automata: characterizations, concepts and open problems
- scientific article; zbMATH DE number 3383997
- Some characterizations of multihead finite automata
- A NOTE ON MULTIHEAD FINITE-STATE AUTOMATA
- On multi-head automata with restricted nondeterminism
- scientific article; zbMATH DE number 1015106
- Multi-head finite automata: Data-independent versus data-dependent computations
- scientific article; zbMATH DE number 1361488
- scientific article; zbMATH DE number 4143455
- Finite dP Automata versus Multi-head Finite Automata
Cites work
- scientific article; zbMATH DE number 3936518 (Why is no real title available?)
- scientific article; zbMATH DE number 3690693 (Why is no real title available?)
- scientific article; zbMATH DE number 3471609 (Why is no real title available?)
- scientific article; zbMATH DE number 3568031 (Why is no real title available?)
- scientific article; zbMATH DE number 1222567 (Why is no real title available?)
- scientific article; zbMATH DE number 2038729 (Why is no real title available?)
- scientific article; zbMATH DE number 3254905 (Why is no real title available?)
- scientific article; zbMATH DE number 3254906 (Why is no real title available?)
- scientific article; zbMATH DE number 3293666 (Why is no real title available?)
- scientific article; zbMATH DE number 3302285 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- k + 1 Heads Are Better than k
- A note on semilinear sets and bounded-reversal multihead pushdown automata
- A note on the succinctness of descriptions of deterministic languages
- A regularity test for pushdown machines
- A useful device for showing the solvability of some decision problems
- Bounded-reversal multihead finite automata languages
- Church-Rosser Thue systems and formal languages
- Classes of languages and linear-bounded automata
- Converting two-way nondeterministic unary automata into simpler automata.
- Descriptional complexity of bounded context-free languages
- Descriptional complexity of machines with limited resources
- Finite automata and unary languages
- Fooling a two-way nondeterministic multihead automaton with reversal number restriction
- Growing context-sensitive languages and Church-Rosser languages
- Language recognition by marking automata
- Lower bounds on the size of sweeping automata
- Mathematical Foundations of Computer Science 2005
- Multi-head finite automata: Data-independent versus data-dependent computations
- Multiprocessor automata
- NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES
- Nondeterminism and the size of two way finite automata
- On 3-head versus 2-head finite automata
- On Communicating Finite-State Machines
- On Context-Free Languages
- On Goedel speed-up and succinctness of language representations
- On Multi-Head Finite Automata
- On non-determinacy in simple computing devices
- On partially blind multihead finite automata.
- On tape-bounded complexity classes and multihead finite automata
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- On the Computational Capacity of Parallel Communicating Finite Automata
- On the Succinctness of Different Representations of Languages
- On the descriptional power of heads, counters, and pebbles
- PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES
- Relations Among Complexity Measures
- Returning and non-returning parallel communicating finite automata are equivalent
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- State-complexity of finite-state devices, state compressibility and incompressibility
- Succinctness of Descriptions of Unambiguous Context-Free Languages
- THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
- The network complexity and the Turing machine complexity of finite functions
- Tight lower bounds on the size of sweeping automata
Cited in
(29)- Real-time, constant-space, constant-randomness verifiers
- Reversibility of computations in graph-walking automata
- From Nondeterministic to Multi-Head Deterministic Finite-State Transducers
- A deterministic two-way multi-head finite automaton can be converted into a reversible one with the same number of heads
- Tight hierarchy of data-independent multi-head automata
- Iterated uniform finite-state transducers on unary languages
- On multi-head automata with restricted nondeterminism
- Constant-space, constant-randomness verifiers with arbitrarily small error
- Multi-head finite automata: characterizations, concepts and open problems
- Finite dP Automata versus Multi-head Finite Automata
- scientific article; zbMATH DE number 1361488 (Why is no real title available?)
- Descriptional complexity of two-way pushdown automata with restricted head reversals
- P and dP automata: unconventional versus classical automata
- Oblivious two-way finite automata: decidability and complexity
- Descriptional complexity of two-way pushdown automata with restricted head reversals
- Diving into the queue
- Iterated uniform finite-state transducers on unary languages
- Queue Automata: Foundations and Developments
- Automata with modulo counters and nondeterministic counter bounds
- On the power of two-way multihead quantum finite automata
- Inside the class of REGEX languages
- A NOTE ON MULTIHEAD FINITE-STATE AUTOMATA
- Multi-head finite automata: Data-independent versus data-dependent computations
- Automata with modulo counters and nondeterministic counter bounds
- Some characterizations of multihead finite automata
- Stateless one-way multi-head finite automata with pebbles
- Frugal encoding in reversible \(\mathcal{MOQA}\): a case study for Quicksort
- Head and state hierarchies for unary multi-head finite automata
- Real-time, constant-space, constant-randomness verifiers
This page was built for publication: Complexity of multi-head finite automata: origins and directions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616495)
