Name
Abstract | ||
|---|---|---|
We look at NFAs augmented with multiple reversal-bounded counters where, during an accepting computation, the behavior of the counters during increasing and decreasing phases is specified by some fixed \"pattern\". We consider families of languages defined by various pattern behaviors and show that some correspond to the smallest full trios containing restricted classes of bounded semilinear languages. For example, one such family is exactly the smallest full trio containing all the bounded semilinear languages. Another family is the smallest full trio containing all the bounded context-free languages. Still another is the smallest full trio containing all bounded languages whose Parikh map is a semilinear set where all periodic vectors have at most two non-zero coordinates. We also examine relationships between the families. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-662-53132-7_18 | Theoretical Computer Science |
Keywords | Field | DocType |
Counter machines, Full trios, Semilinearity, Bounded languages | Counter machine,Discrete mathematics,Combinatorics,Periodic graph (geometry),Mathematics,Bounded function,Computation | Conference |
Volume | ISSN | Citations |
799 | 0302-9743 | 1 |
PageRank | References | Authors |
0.40 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oscar H. Ibarra | 1 | 3235 | 741.44 |
| Ian McQuillan | 2 | 97 | 24.72 |