An extended direct branching algorithm for checking equivalence of deterministic pushdown automata (Q801689)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3880133
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | An extended direct branching algorithm for checking equivalence of deterministic pushdown automata |
scientific article; zbMATH DE number 3880133 |
Statements
An extended direct branching algorithm for checking equivalence of deterministic pushdown automata (English)
0 references
1984
0 references
This paper extends the author's direct branching algorithm [Inf. Control. 52, 187-238 (1982; Zbl 0541.68053)] for checking equivalence of deterministic pushdown automata. It does so by providing a technique called 'halting' for dealing with nodes with unbounded degree in the comparison tree. This may occur when a skipping step may be applied infinitely many times to a certain node, as a result of infinite sequences of \(\epsilon\)-moves. This extension allows the algorithm to check equivalence of the deterministic pushdown automata when none of them is real-time, but in a certain condition that properly contains a case where one of them is real-time strict.
0 references
direct branching algorithm
0 references
equivalence of deterministic pushdown automata
0 references
comparison tree
0 references
0 references
0 references
0 references
0 references
0 references
0.7612870931625366
0 references
0.7515827417373657
0 references
0.7454308867454529
0 references
0.7386548519134521
0 references
0.734286367893219
0 references
