Paper Info
Title
Semilinearity Of Families Of Languages
Abstract
Techniques are developed for creating new and general language families of only semilinear languages, and for showing families only contain semilinear languages. It is shown that for language families Script capital L that are semilinear full trios, the smallest full AFL containing Script capital L that is also closed under intersection with languages in NCM (where NCM is the family of languages accepted by NFAs augmented with reversal-bounded counters), is also semilinear. If these closure properties are effective, this also immediately implies decidability of membership, emptiness, and infiniteness for these general families. From the general techniques, new grammar systems are given that are extensions of well-known families of semilinear full trios, whereby it is implied that these extensions must only describe semilinear languages. This also implies positive decidability properties for the new systems. Some characterizations of the new families are also given.
Year
DOI
Venue
2020
10.1142/S0129054120420095
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Keywords
DocType
Volume
Semilinearity, closure properties, counter machines, pushdown automata, decidability
Journal
31
Issue
ISSN
Citations 
8
0129-0541
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Oscar H. Ibarra13235741.44
Ian McQuillan29724.72