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
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