Some results on the generalized star-height problem

DOI10.1016/0890-5401(92)90063-LzbMath0769.68066WikidataQ56388123 ScholiaQ56388123MaRDI QIDQ1207944

Jean-Eric 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)

Related Items (11)

Shuffle on positive varieties of languages ⋮ On the star-height of subword counting languages and their relationship to Rees zero-matrix semigroups ⋮ The Transitivity Problem of Turing Machines ⋮ Monadic partition logics and finite automata ⋮ More languages of generalised star height 1 ⋮ Some results on the generalized star-height problem ⋮ EQUATIONAL DESCRIPTIONS OF LANGUAGES ⋮ Group presentations, formal languages and characterizations of one- counter groups ⋮ Some results onC-varieties ⋮ Classes of languages generated by the Kleene star of a word ⋮ Classifying regular languages by a split game

Cites Work

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

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