DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ (Q5495414): Difference between revisions

Revision as of 20:45, 8 July 2024

scientific article; zbMATH DE number 6324612

Language	Label	Description	Also known as
English	DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ	scientific article; zbMATH DE number 6324612

Statements

instance of

scholarly article

0 references

title

DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ (English)

0 references

0 references

0 references

0 references

0 references

International Journal of Foundations of Computer Science

0 references

publication date

4 August 2014

0 references

zbMATH Keywords

nondeterminism

0 references

two-way finite automata

0 references

state complexity

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Finite automata and unary languages

0 references

Magic numbers in the state hierarchy of finite automata

0 references

Converting two-way nondeterministic unary automata into simpler automata.

0 references

Complementing two-way finite automata

0 references

Two-way unary automata versus logarithmic space

0 references

The power of nondeterminism and randomness for oblivious branching programs

0 references

Size complexity of rotating and sweeping automata

0 references

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

0 references

On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata

0 references

Lower bounds on the size of sweeping automata

0 references

Identifiers

zbMATH Open document ID

1293.68188

0 references

DOI

10.1142/S012905411340025X

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5495414

@@ Property / cites work @@
+Finite automata and unary languages
@@ Property / cites work: Finite automata and unary languages / rank @@
+Normal rank
@@ Property / cites work @@
+Magic numbers in the state hierarchy of finite automata
+Normal rank
@@ Property / cites work @@
+Converting two-way nondeterministic unary automata into simpler automata.
+Normal rank
@@ Property / cites work @@
+Complementing two-way finite automata
@@ Property / cites work: Complementing two-way finite automata / rank @@
+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 @@
+The power of nondeterminism and randomness for oblivious branching programs
+Normal rank
@@ Property / cites work @@
+Size complexity of rotating and sweeping automata
@@ Property / cites work: Size complexity of rotating and sweeping automata / rank @@
+Normal rank
@@ Property / cites work @@
+Two-way deterministic finite automata are exponentially more succinct than sweeping automata
+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 @@
+Lower bounds on the size of sweeping automata
@@ Property / cites work: Lower bounds on the size of sweeping automata / rank @@
+Normal rank