Complexity of multi-head finite automata: origins and directions (Q616495): Difference between revisions

@@ Property / cites work @@
+Q4139689
@@ Property / cites work: Q4139689 / rank @@
+Normal rank
@@ Property / cites work @@
+State-complexity of finite-state devices, state compressibility and incompressibility
+Normal rank
@@ Property / cites work @@
+On the Computational Capacity of Parallel Communicating Finite Automata
+Normal rank
@@ Property / cites work @@
+On Communicating Finite-State Machines
@@ Property / cites work: On Communicating Finite-State Machines / rank @@
+Normal rank
@@ Property / cites work @@
+Multiprocessor automata
@@ Property / cites work: Multiprocessor automata / rank @@
+Normal rank
@@ Property / cites work @@
+Growing context-sensitive languages and Church-Rosser languages
+Normal rank
@@ Property / cites work @@
+Returning and non-returning parallel communicating finite automata are equivalent
+Normal rank
@@ Property / cites work @@
+Finite automata and unary languages
@@ Property / cites work: Finite automata and unary languages / rank @@
+Normal rank
@@ Property / cites work @@
+Converting two-way nondeterministic unary automata into simpler automata.
+Normal rank
@@ Property / cites work @@
+Q5576254
@@ Property / cites work: Q5576254 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5422234
@@ Property / cites work: Q5422234 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5583856
@@ Property / cites work: Q5583856 / rank @@
+Normal rank
@@ Property / cites work @@
+On non-determinacy in simple computing devices
@@ Property / cites work: On non-determinacy in simple computing devices / rank @@
+Normal rank
@@ Property / cites work @@
+On the Succinctness of Different Representations of Languages
+Normal rank
@@ Property / cites work @@
+On Goedel speed-up and succinctness of language representations
+Normal rank
@@ Property / cites work @@
+Multi-head finite automata: Data-independent versus data-dependent computations
+Normal rank
@@ Property / cites work @@
+Q5592246
@@ Property / cites work: Q5592246 / rank @@
+Normal rank
@@ Property / cites work @@
+Fooling a two-way nondeterministic multihead automaton with reversal number restriction
+Normal rank
@@ Property / cites work @@
+Q4449194
@@ Property / cites work: Q4449194 / rank @@
+Normal rank
@@ Property / cites work @@
+A note on semilinear sets and bounded-reversal multihead pushdown automata
+Normal rank
@@ Property / cites work @@
+Reversal-Bounded Multicounter Machines and Their Decision Problems
+Normal rank
@@ Property / cites work @@
+On 3-head versus 2-head finite automata
@@ Property / cites work: On 3-head versus 2-head finite automata / rank @@
+Normal rank
@@ Property / cites work @@
+A useful device for showing the solvability of some decision problems
+Normal rank
@@ Property / cites work @@
+On partially blind multihead finite automata.
@@ Property / cites work: On partially blind multihead finite automata. / rank @@
+Normal rank
@@ Property / cites work @@
+NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES
@@ Property / cites work: NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES / rank @@
+Normal rank
@@ Property / cites work @@
+Mathematical Foundations of Computer Science 2005
@@ Property / cites work: Mathematical Foundations of Computer Science 2005 / rank @@
+Normal rank
@@ Property / cites work @@
+Classes of languages and linear-bounded automata
@@ Property / cites work: Classes of languages and linear-bounded automata / rank @@
+Normal rank
@@ Property / cites work @@
+On the descriptional power of heads, counters, and pebbles
+Normal rank
@@ Property / cites work @@
+THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
@@ Property / cites work: THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS / rank @@
+Normal rank
@@ Property / cites work @@
+Tight lower bounds on the size of sweeping automata
+Normal rank
@@ Property / cites work @@
+Descriptional complexity of bounded context-free languages
+Normal rank
@@ Property / cites work @@
+PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES
+Normal rank
@@ Property / cites work @@
+Church-Rosser Thue systems and formal languages
@@ Property / cites work: Church-Rosser Thue systems and formal languages / rank @@
+Normal rank
@@ Property / cites work @@
+Q3885190
@@ Property / cites work: Q3885190 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
+Normal rank
@@ Property / cites work @@
+On Context-Free Languages
@@ Property / cites work: On Context-Free Languages / rank @@
+Normal rank
@@ Property / cites work @@
+Q4055196
@@ Property / cites work: Q4055196 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4218105
@@ Property / cites work: Q4218105 / rank @@
+Normal rank
@@ Property / cites work @@
+Relations Among Complexity Measures
@@ Property / cites work: Relations Among Complexity Measures / rank @@
+Normal rank
@@ Property / cites work @@
+Q5541339
@@ Property / cites work: Q5541339 / rank @@
+Normal rank
@@ Property / cites work @@
+Language recognition by marking automata
@@ Property / cites work: Language recognition by marking automata / rank @@
+Normal rank
@@ Property / cites work @@
+On Multi-Head Finite Automata
@@ Property / cites work: On Multi-Head Finite Automata / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterminism and the size of two way finite automata
+Normal rank
@@ Property / cites work @@
+Succinctness of Descriptions of Unambiguous Context-Free Languages
+Normal rank
@@ Property / cites work @@
+The network complexity and the Turing machine complexity of finite functions
+Normal rank
@@ Property / cites work @@
+Q5541340
@@ Property / cites work: Q5541340 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds on the size of sweeping automata
@@ Property / cites work: Lower bounds on the size of sweeping automata / rank @@
+Normal rank
@@ Property / cites work @@
+A regularity test for pushdown machines
@@ Property / cites work: A regularity test for pushdown machines / rank @@
+Normal rank
@@ Property / cites work @@
+Bounded-reversal multihead finite automata languages
+Normal rank
@@ Property / cites work @@
+On tape-bounded complexity classes and multihead finite automata
+Normal rank
@@ Property / cites work @@
+A note on the succinctness of descriptions of deterministic languages
+Normal rank
@@ Property / cites work @@
+Q3707407
@@ Property / cites work: Q3707407 / rank @@
+Normal rank
@@ Property / cites work @@
+<i>k</i>             + 1 Heads Are Better than             <i>k</i>
@@ Property / cites work: <i>k</i> + 1 Heads Are Better than <i>k</i> / rank @@
+Normal rank