A graph-based regularity test for deterministic context-free languages (Q1177178): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 00:34, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A graph-based regularity test for deterministic context-free languages |
scientific article |
Statements
A graph-based regularity test for deterministic context-free languages (English)
0 references
26 June 1992
0 references
It is shown that there exists a test of complexity \(O((qt)^ 2 t^{qt})\) for testing the regularity of a deterministic context-free language, where \(q\) is the number of states and \(t\) is the stack alphabet size of the pushdown automaton derived from an \(LR(1)\) grammar for the languages. The previously established upper bound for the test was \(t^{q^ q}\).
0 references
context-free languages
0 references
pushdown automata
0 references
