Improved limitedness theorems on finite automata with distance functions

DOI10.1016/0304-3975(90)90044-IzbMath0693.68031OpenAlexW2046829789MaRDI QIDQ908702

Kosaburo Hashiguchi

Publication date: 1990

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(90)90044-i

zbMATH Keywords

upper boundfinite automatondistance function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (29)

Two techniques in the area of the star problem in trace monoids ⋮ The limitedness problem on distance automata: Hashiguchi's method revisited ⋮ Methods and applications of (max,+) linear algebra ⋮ Finite-valued distance automata ⋮ Exponential upper and lower bounds for the order of a regular language ⋮ Trading Bounds for Memory in Games with Counters ⋮ Distance desert automata and the star height problem ⋮ On the Burnside problem for semigroups of matrices in the \((\max,+)\) algebra ⋮ On finite automata with limited nondeterminism (extended abstract) ⋮ Bounded repairability of word languages ⋮ Distance automata having large finite distance or finite ambiguity ⋮ A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata ⋮ Inclines and incline matrices: A survey. ⋮ R-Automata ⋮ The product of rational languages ⋮ On semigroups of matrices over the tropical semiring ⋮ Algorithms for determining relative inclusion star height and inclusion star height ⋮ Universality of R-automata with Value Copying ⋮ Regular path queries under approximate semantics ⋮ Bounded regular path queries in view-based data integration ⋮ The closure under division and a characterization of the recognizable $\mathcal {Z}$-subsets ⋮ REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS ⋮ Weighted automata ⋮ New upper bounds to the limitedness of distance automata ⋮ The finite power problem revisited. ⋮ Limitedness theorem on finite automata with distance functions: An algebraic proof ⋮ Distances between languages and reflexivity of relations ⋮ The finite power property in free groups ⋮ Some properties of recognizable \(\mathcal Z\)-subsets

Cites Work

• Unnamed Item
• Unnamed Item
• Limitedness theorem on finite automata with distance functions
• Representation theorems on regular languages
• A decision procedure for the order of regular events
• Regular languages of star height one

This page was built for publication: Improved limitedness theorems on finite automata with distance functions