Paper Info
Title
On Bounded Semilinear Languages, Counter Machines, And Finite-Index Et0l
Abstract
We show that for every trio L containing only semilinear languages, all bounded languages in L can be accepted by one-way nondeterministic reversal-bounded multicounter machines (NCM), and in fact, even by the deterministic versions of these machines (DCM). This implies that for every semilinear trio (where these properties are effective), it is possible to decide containment, equivalence, and disjointness concerning its bounded languages. We also provide a relatively simple condition for when the bounded languages in a semilinear trio coincide exactly with those accepted by DCM machines. This is applied to finite-index ET0L systems, where we show that the bounded languages generated by these systems are exactly the bounded languages accepted by DCM. We also define, compare, and characterize several other types of languages that are both bounded and semilinear.
Year
DOI
Venue
2016
10.1007/978-3-319-40946-7_12
Implementation and Application of Automata
Field
DocType
Volume
Discrete mathematics,Nondeterministic algorithm,Theoretical computer science,Equivalence (measure theory),Mathematics,Bounded function
Conference
9705
ISSN
Citations 
PageRank 
0302-9743
3
0.47
References 
Authors
7
2
Name
Order
Citations
PageRank
Oscar H. Ibarra13235741.44
Ian McQuillan29724.72