Some results on the generalized star-height problem

DOI10.1016/0890-5401(92)90063-LMaRDI QIDQ1207944zbMATH OpenWikidataFDO

Authors Jean-Éric Pin, Howard Straubing, Denis Thérien

Publication date 16 May 1993

Published in Information and Computation (Search for Journal in Brave)

zbMATH Keywords

nilpotent groupsrational languagegeneralized star-height problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Recommendations

• Open problems about regular languages, 35 years later
• On the starheight of some rational subsets closed under partial commutations
• On the complexity of the relative inclusion star height problem
• Some Variants of the Star Height Problem
• Distance desert automata and the star height problem

Cites work

• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 3654376 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• AUTOMATE, a computing package for automata and finite semigroups
• Aperiodic homomorphisms and the concatenation product of recognizable sets
• Complexity of some problems from the theory of automata
• Computer proofs of limit theorems
• On finite monoids having only trivial subgroups
• Remark on the star-height-problem
• Representation theorems on regular languages
• Some results on the generalized star-height problem

Cited in

(18)

• Some results onC-varieties
• scientific article; zbMATH DE number 2086220 (Why is no real title available?)
• Some Variants of the Star Height Problem
• Open problems about regular languages, 35 years later
• The transitivity problem of Turing machines
• Shuffle on positive varieties of languages
• Group presentations, formal languages and characterizations of one- counter groups
• Distance desert automata and the star height problem
• On the starheight of some rational subsets closed under partial commutations
• Classifying regular languages by a split game
• Classes of languages generated by the Kleene star of a word
• More languages of generalised star height 1
• On the star-height of subword counting languages and their relationship to Rees zero-matrix semigroups
• The solutions of two star-height problems for regular trees
• Some results on the generalized star-height problem
• Equational descriptions of languages
• An application of Cohen's result on star height to the theory of control structures
• Monadic partition logics and finite automata

This page was built for publication: Some results on the generalized star-height problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1207944)