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