Some results on the generalized star-height problem

DOI10.1016/0890-5401(92)90063-LzbMATH Open0769.68066WikidataQ56388123 ScholiaQ56388123MaRDI QIDQ1207944FDOQ1207944

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

Publication date: 16 May 1993

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

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

zbMATH Keywords

nilpotent groupsrational languagegeneralized star-height problem

Mathematics Subject Classification ID

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

Cites Work

• AUTOMATE, a computing package for automata and finite semigroups
• Complexity of some problems from the theory of automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On finite monoids having only trivial subgroups
• Title not available (Why is that?)
• Representation theorems on regular languages
• Some results on the generalized star-height problem
• Computer proofs of limit theorems
• Aperiodic homomorphisms and the concatenation product of recognizable sets
• Remark on the star-height-problem

Cited In (18)

• Some results onC-varieties
• Title not available (Why is that?)
• 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
• Equational descriptions of languages
• Some results on the generalized star-height problem
• 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)