Distance desert automata and the star height problem

DOI10.1051/ita:2005027zbMath1082.20041OpenAlexW2095067686WikidataQ56061219 ScholiaQ56061219MaRDI QIDQ5313718

Daniel Kirsten

Publication date: 1 September 2005

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2005__39_3_455_0

zbMATH Keywords

decidabilityhierarchiesfree monoidsrecognizable languagesdistance automatadesert automatastar height problemstar heights

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (20)

Approximate comparison of functions computed by distance automata ⋮ Trading Bounds for Memory in Games with Counters ⋮ Stamina: stabilisation monoids in automata theory ⋮ Concatenation hierarchies: new bottle, old wine ⋮ Closure properties and complexity of rational sets of regular languages ⋮ The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata ⋮ Finite Automata, Digraph Connectivity, and Regular Expression Size ⋮ A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata ⋮ Unnamed Item ⋮ The Nesting-Depth of Disjunctive μ-Calculus for Tree Languages and the Limitedness Problem ⋮ R-Automata ⋮ Limited Non-determinism Hierarchy of Counter Automata ⋮ Weak MSO with the unbounding quantifier ⋮ Universality of R-automata with Value Copying ⋮ Bounded regular path queries in view-based data integration ⋮ Factorization Forests ⋮ Generic results for concatenation hierarchies ⋮ Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring ⋮ Automata and rational expressions ⋮ Weighted automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Limitedness theorem on finite automata with distance functions: An algebraic proof
• Improved limitedness theorems on finite automata with distance functions
• Limitedness theorem on finite automata with distance functions
• Representation theorems on regular languages
• On the topological structure of a finitely generated semigroup of matrices
• Algorithms for determining relative star height and star height
• On finite automata with limited nondeterminism
• Parametrized recurrent systems for image generation
• Finite-valued distance automata
• New upper bounds to the limitedness of distance automata
• Two techniques in the area of the star problem in trace monoids
• The limitedness problem on distance automata: Hashiguchi's method revisited
• New results on the star problem in trace monoids
• A Burnside approach to the finite substitution problem
• Transition graphs and the star-height of regular events
• Star height of certain families of regular events
• Regular languages of star height one
• Distance automata having large finite distance or finite ambiguity
• Homomorphisms that preserve star height
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
• ON THE STAR HEIGHT OF RATIONAL LANGUAGES
• On semigroups of matrices over the tropical semiring
• Foundations of Software Science and Computation Structures
• STACS 2004
• STACS 2004
• On a question of Eggan

This page was built for publication: Distance desert automata and the star height problem