Paper Info
Title
Relationships Between Bounded Languages, Counter Machines, Finite-Index Grammars, Ambiguity, And Commutative Regularity
Abstract
It is shown that for every language family that is a trio containing only semilinear languages, all bounded languages in it can be accepted by one-way deterministic reversal-bounded multicounter 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. A condition is also provided for when the bounded languages in a semilinear trio coincide exactly with those accepted by DCM machines, and it is used to show that many grammar systems of finite index - such as finite-index matrix grammars (M-fin) and finite-index ETOL (ETOLfin) - have identical bounded languages as DCM.Then connections between ambiguity, counting regularity, and commutative regularity are made, as many machines and grammars that are unambiguous can only generate/accept counting regular or commutatively regular languages. Thus, such a system that can generate/accept a non-counting regular or non-commutatively regular language implies the existence of inherently ambiguous languages over that system. In addition, it is shown that every language generated by an unambiguous M-fin has a rational characteristic series in commutative variables, and is counting regular. This result plus the connections are used to demonstrate that the grammar systems M-fin and ETOLfin can generate inherently ambiguous languages (over their grammars), as do several machine models. It is also shown that all bounded languages generated by these two grammar systems (those in any semilinear trio) can be generated unambiguously within the systems. Finally, conditions on M-fin and ETOLfin languages implying commutative regularity are obtained. In particular, it is shown that every finite-index EDOL language is commutatively regular. (C) 2020 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2021
10.1016/j.tcs.2020.10.006
THEORETICAL COMPUTER SCIENCE
Keywords
DocType
Volume
ETOL systems, Matrix grammars, Rational series, Commutative equivalence, Counter machines
Journal
862
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Arturo Carpi125531.99
Flavio Dalessandro262.32
Oscar H. Ibarra301.35
Ian McQuillan49724.72