Algorithms for determining relative star height and star height
type: Item
instance of: scholarly article
title: Algorithms for determining relative star height and star height
zbMATH Open document ID: 0668.68081
DOI: 10.1016/0890-5401(88)90033-8
author: Kosaburo Hashiguchi
published in: Information and Computation
publication date: 1988-01-01T00:00:00Z
review text: Let R be a regular language and \({\mathcal C}=(R_ 1,R_ 2,...,R_ m)\) be a finite set of regular languages. The relative star height of R with respect to \({\mathcal C}\) is the minimum star height of regular languages which can be transformed into R by substituting alphabetic symbols on languages from \({\mathcal C}\). This paper proves the existence of algorithm for determining the relative star height. This evidently implies the solvability of determining the star height for any regular language. The suggested algorithm is quite complex.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4094843
zbMATH Keywords: regular language
zbMATH Keywords: relative star height
Wikidata QID: Q56061218
reviewed by: Anatoly V. Anisimov
MaRDI profile type: Publication
full work available at URL: 0890-5401(88)90033-8
OpenAlex ID: W2151259840
cites work: The solutions of two star-height problems for regular trees
cites work: Roots of Star Events
cites work: Star height of certain families of regular events
cites work: Techniques for establishing star height of regular sets
cites work: General properties of star height of regular events
cites work: On a question of Eggan
cites work: Transition graphs and the star-height of regular events
cites work: A decision procedure for the order of regular events
cites work: Limitedness theorem on finite automata with distance functions
cites work: Regular languages of star height one
cites work: Representation theorems on regular languages
cites work: Homomorphisms that preserve star height
cites work: The star height of reset-free events and strictly locally testable events
cites work: Q4401426
cites work: The loop complexity of pure-group events
cites work: Q3026370
DBLP publication ID: journals/iandc/Hashiguchi88
description: scientific article; zbMATH DE number 4094843