Name
Abstract | ||
|---|---|---|
A language L is said to be dense if every word in the universe is an infix of some word in L. This notion has been generalized from the infix operation to arbitrary word operations 6, in place of the infix operation (rho-dense, with infix-dense being the standard notion of dense). It is shown here that it is decidable, for a language L accepted by a one-way non deterministic reversal-bounded pushdown automaton, whether L is infix-dense. However, it becomes undecidable for both deterministic pushdown automata (with no reversal bound), and for nondeterministic one-counter automata. When examining suffix-density, it is undecidable for more restricted families such as deterministic one-counter automata that make three reversals on the counter, but it is decidable with less reversals. Other decidability results are also presented on dense languages, and contrasted with a marked version called rho-marked-density. Also, new languages are demonstrated to be outside various deterministic language families after applying different deletion operations from smaller families. Lastly, bounded-dense languages are defined and examined. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1142/S0129054118400051 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
Counter machines, pushdown automata, decidability, density, deletion | Discrete mathematics,Context-free language,Combinatorics,Nested word,Nondeterministic algorithm,Deterministic pushdown automaton,Infix,Decidability,Pushdown automaton,Mathematics,Undecidable problem | Conference |
Volume | Issue | ISSN |
29 | 2 | 0129-0541 |
Citations | PageRank | References |
1 | 0.38 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joey Eremondi | 1 | 8 | 1.65 |
| Oscar H. Ibarra | 2 | 3235 | 741.44 |
| Ian McQuillan | 3 | 97 | 24.72 |