Limitedness theorem on finite automata with distance functions
From MaRDI portal
Publication:1050772
DOI10.1016/0022-0000(82)90051-4zbMath0513.68051OpenAlexW2165854715MaRDI QIDQ1050772
Publication date: 1982
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(82)90051-4
Related Items (50)
Some consequences of a Fatou property of the tropical semiring ⋮ Equational theories of tropical semirings ⋮ DECIDABILITY OF THE EQUIVALENCE PROBLEM FOR FINITELY AMBIGUOUS FINANCE AUTOMATA ⋮ Approximate comparison of functions computed by distance automata ⋮ Two techniques in the area of the star problem in trace monoids ⋮ The limitedness problem on distance automata: Hashiguchi's method revisited ⋮ A complete system of identities for one-letter rational expressions with multiplicities in the tropical semiring ⋮ Finite-valued distance automata ⋮ Exponential upper and lower bounds for the order of a regular language ⋮ On the topological structure of a finitely generated semigroup of matrices ⋮ Distance desert automata and the star height problem ⋮ Fuzzy \(h\)-ideals of hemirings. ⋮ On the Burnside problem for semigroups of matrices in the \((\max,+)\) algebra ⋮ Algorithms for determining relative star height and star height ⋮ On finite automata with limited nondeterminism (extended abstract) ⋮ Closure properties and complexity of rational sets of regular languages ⋮ Distance automata having large finite distance or finite ambiguity ⋮ Foundations of graph path query languages. Course notes for the reasoning web summer school 2021 ⋮ Existential and universal width of alternating finite automata ⋮ Improved limitedness theorems on finite automata with distance functions ⋮ Factorization forests of finite height ⋮ On measuring nondeterminism in regular languages ⋮ R-Automata ⋮ The product of rational languages ⋮ On semigroups of matrices over the tropical semiring ⋮ Polynomial operations and hierarchies of concatenation ⋮ Algorithms for determining relative inclusion star height and inclusion star height ⋮ Rational relations and rational series ⋮ Sequential? ⋮ Universality of R-automata with Value Copying ⋮ Unnamed Item ⋮ Regular path queries under approximate semantics ⋮ Unnamed Item ⋮ Bounded regular path queries in view-based data integration ⋮ Factorization Forests ⋮ The closure under division and a characterization of the recognizable $\mathcal {Z}$-subsets ⋮ What's decidable about weighted automata? ⋮ MEMBERSHIP AND FINITENESS PROBLEMS FOR RATIONAL SETS OF REGULAR LANGUAGES ⋮ REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS ⋮ The factorisation forest theorem ⋮ New upper bounds to the limitedness of distance automata ⋮ On the power of circular splicing ⋮ SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS ⋮ Representation theorems on regular languages ⋮ The finite power problem revisited. ⋮ Weak Cost Register Automata are Still Powerful ⋮ 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
This page was built for publication: Limitedness theorem on finite automata with distance functions
