Two-way automata making choices only at the endmarkers (Q476168): Difference between revisions

Latest revision as of 09:36, 9 July 2024

scientific article; zbMATH DE number 6044348

Two-Way Automata Making Choices Only at the Endmarkers

Language	Label	Description	Also known as
English	Two-way automata making choices only at the endmarkers	scientific article; zbMATH DE number 6044348	Two-Way Automata Making Choices Only at the Endmarkers

Statements

instance of

scholarly article

0 references

title

Two-way automata making choices only at the endmarkers (English)

0 references

Two-Way Automata Making Choices Only at the Endmarkers (English)

0 references

zbMATH Open document ID

1309.68119

0 references

1351.68138

0 references

DOI

10.1016/j.ic.2014.08.009

0 references

10.1007/978-3-642-28332-1_23

0 references

0 references

0 references

0 references

Information and Computation

0 references

Language and Automata Theory and Applications

0 references

publication date

28 November 2014

0 references

8 June 2012

0 references

full work available at URL

https://arxiv.org/abs/1110.1263

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

two-way automata

0 references

descriptional complexity

0 references

regular languages

0 references

MaRDI profile type

MaRDI publication profile

0 references

0 references

0 references

0 references

0 references

0 references

Nondeterminism and the size of two way finite automata

0 references

Lower bounds on the size of sweeping automata

0 references

Q3938525

0 references

Two-way deterministic finite automata are exponentially more succinct than sweeping automata

0 references

Q4449194

0 references

Nondeterminism is essential in small two-way finite automata with few reversals

0 references

Converting two-way nondeterministic unary automata into simpler automata.

0 references

Two-way unary automata versus logarithmic space

0 references

Q4139689

0 references

Two-Way Automata versus Logarithmic Space

0 references

Two-Way Automata Characterizations of L/poly versus NL

0 references

Complementing two-way finite automata

0 references

Small Sweeping 2NFAs Are Not Closed Under Complement

0 references

Size Complexity of Two-Way Finite Automata

0 references

An alternating hierarchy for finite automata

0 references

Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations

0 references

Halting space-bounded computations

0 references

Q3862379

0 references

Turing machines with sublogarithmic space

0 references

Relationships between nondeterministic and deterministic tape complexities

0 references

Making Nondeterminism Unambiguous

0 references

Turing machines that take advice

0 references

Alternation

0 references

Number of quantifiers is better than number of tape cells

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:476168

@@ Property / cites work @@
+Nondeterminism and the size of two way finite automata
+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 @@
+Q3938525
@@ Property / cites work: Q3938525 / rank @@
+Normal rank
@@ Property / cites work @@
+Two-way deterministic finite automata are exponentially more succinct than sweeping automata
+Normal rank
@@ Property / cites work @@
+Q4449194
@@ Property / cites work: Q4449194 / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterminism is essential in small two-way finite automata with few reversals
+Normal rank
@@ Property / cites work @@
+Converting two-way nondeterministic unary automata into simpler automata.
+Normal rank
@@ Property / cites work @@
+Two-way unary automata versus logarithmic space
@@ Property / cites work: Two-way unary automata versus logarithmic space / rank @@
+Normal rank
@@ Property / cites work @@
+Q4139689
@@ Property / cites work: Q4139689 / rank @@
+Normal rank
@@ Property / cites work @@
+Two-Way Automata versus Logarithmic Space
@@ Property / cites work: Two-Way Automata versus Logarithmic Space / rank @@
+Normal rank
@@ Property / cites work @@
+Two-Way Automata Characterizations of L/poly versus NL
+Normal rank
@@ Property / cites work @@
+Complementing two-way finite automata
@@ Property / cites work: Complementing two-way finite automata / rank @@
+Normal rank
@@ Property / cites work @@
+Small Sweeping 2NFAs Are Not Closed Under Complement
+Normal rank
@@ Property / cites work @@
+Size Complexity of Two-Way Finite Automata
@@ Property / cites work: Size Complexity of Two-Way Finite Automata / rank @@
+Normal rank
@@ Property / cites work @@
+An alternating hierarchy for finite automata
@@ Property / cites work: An alternating hierarchy for finite automata / rank @@
+Normal rank
@@ Property / cites work @@
+Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
+Normal rank
@@ Property / cites work @@
+Halting space-bounded computations
@@ Property / cites work: Halting space-bounded computations / rank @@
+Normal rank
@@ Property / cites work @@
+Q3862379
@@ Property / cites work: Q3862379 / rank @@
+Normal rank
@@ Property / cites work @@
+Turing machines with sublogarithmic space
@@ Property / cites work: Turing machines with sublogarithmic space / rank @@
+Normal rank
@@ Property / cites work @@
+Relationships between nondeterministic and deterministic tape complexities
+Normal rank
@@ Property / cites work @@
+Making Nondeterminism Unambiguous
@@ Property / cites work: Making Nondeterminism Unambiguous / rank @@
+Normal rank
@@ Property / cites work @@
+Turing machines that take advice
@@ Property / cites work: Turing machines that take advice / rank @@
+Normal rank
@@ Property / cites work @@
+Alternation
@@ Property / cites work: Alternation / rank @@
+Normal rank
@@ Property / cites work @@
+Number of quantifiers is better than number of tape cells
+Normal rank