Pages that link to "Item:Q5402568"

The following pages link to Nondeterminism and the size of two way finite automata (Q5402568):

Displaying 50 items.

• Size complexity of rotating and sweeping automata (Q414916) (← links)
• An alternating hierarchy for finite automata (Q442279) (← links)
• Two-way automata making choices only at the endmarkers (Q476168) (← links)
• Two double-exponential gaps for automata with a limited pushdown (Q515677) (← links)
• Two-way unary automata versus logarithmic space (Q549665) (← links)
• Complexity of multi-head finite automata: origins and directions (Q616495) (← links)
• Two-way deterministic automata with two reversals are exponentially more succinct than with one reversal (Q656586) (← links)
• Partial orders on words, minimal elements of regular languages, and state complexity (Q688156) (← links)
• On NFAs where all states are final, initial, or both (Q1034621) (← links)
• Finite automata and unary languages (Q1099644) (← links)
• A note on the reduction of two-way automata to one-way automata (Q1116341) (← links)
• Tradeoffs for language recognition on alternating machines (Q1117697) (← links)
• Halting space-bounded computations (Q1134515) (← links)
• Lower bounds on the size of sweeping automata (Q1145513) (← links)
• Two-way deterministic finite automata are exponentially more succinct than sweeping automata (Q1157965) (← links)
• Fooling a two way automaton or one pushdown store is better than one counter for two way machines (Q1165027) (← links)
• Intersection and union of regular languages and state complexity (Q1199879) (← links)
• Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations (Q1201150) (← links)
• Converting two-way nondeterministic unary automata into simpler automata. (Q1401239) (← links)
• From bidirectionality to alternation. (Q1401248) (← links)
• The size of power automata. (Q1401251) (← links)
• Tight lower bounds on the size of sweeping automata (Q1604196) (← links)
• State complexity of some operations on binary regular languages (Q1763716) (← links)
• On the descriptional power of heads, counters, and pebbles (Q1763719) (← links)
• On multi-partition communication complexity (Q1886038) (← links)
• New size hierarchies for two way automata (Q1992112) (← links)
• Alternation in two-way finite automata (Q2029487) (← links)
• Converting nondeterministic two-way automata into small deterministic linear-time machines (Q2105419) (← links)
• On the transformation of two-way deterministic finite automata to unambiguous finite automata (Q2232267) (← links)
• Oblivious two-way finite automata: decidability and complexity (Q2252534) (← links)
• Two-way automata versus logarithmic space (Q2254505) (← links)
• Nondeterministic complexity in subclasses of convex languages (Q2319915) (← links)
• Two-way automata characterizations of L/poly versus NL (Q2354593) (← links)
• Boolean language operations on nondeterministic automata with a pushdown of constant height (Q2403237) (← links)
• Magic numbers in the state hierarchy of finite automata (Q2461796) (← links)
• Infinite vs. finite size-bounded randomized computations (Q2637645) (← links)
• Complementing two-way finite automata (Q2643079) (← links)
• Improved complement for two-way alternating automata (Q2675811) (← links)
• Both Ways Rational Functions (Q2817380) (← links)
• Two-Way Automata in Coq (Q2829256) (← links)
• Self-Verifying Finite Automata and Descriptional Complexity (Q2829967) (← links)
• Operations on Weakly Recognizing Morphisms (Q2829976) (← links)
• Translation from classical two-way automata to pebble two-way automata (Q2998731) (← links)
• Two-Way Automata versus Logarithmic Space (Q3007639) (← links)
• Nondeterminism Is Essential in Small 2FAs with Few Reversals (Q3012920) (← links)
• On the Size of Two-Way Reasonable Automata for the Liveness Problem (Q3451094) (← links)
• On the State Complexity of Complements, Stars, and Reversals of Regular Languages (Q3533030) (← links)
• On the State Complexity of Operations on Two-Way Finite Automata (Q3533031) (← links)
• On the Size Complexity of Rotating and Sweeping Automata (Q3533032) (← links)
• From Philosophical to Industrial Logics (Q3601803) (← links)