ISSN:
1432-0525
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Summary A dual bordered OS system is a triple (∑, P, S) where ∑ is a finite alphabet, S a finite subset of ∑*, the set of axioms, and P a finite set of rules of the form a→a × a, where a ε ∑ and x ε ∑ *. Using well-quasi-order theory, we show that the regularity problem for such systems is decidable. Whether such a system generates a regular language essentially only depends on the set of rules but not on the axioms.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00289112
Permalink