Limitedness theorem on finite automata with distance functions: An algebraic proof
From MaRDI portal
Publication:807031
DOI10.1016/0304-3975(91)90321-RzbMath0729.68049MaRDI QIDQ807031
Publication date: 1991
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
The limitedness problem on distance automata: Hashiguchi's method revisited, Methods and applications of (max,+) linear algebra, Finite-valued distance automata, Trading Bounds for Memory in Games with Counters, Distance desert automata and the star height problem, On finite automata with limited nondeterminism (extended abstract), Distance automata having large finite distance or finite ambiguity, Existential and universal width of alternating finite automata, A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata, R-Automata, Universality of R-automata with Value Copying, Regular path queries under approximate semantics, Unnamed Item, 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, The factorisation forest theorem, New upper bounds to the limitedness of distance automata, Some properties of recognizable \(\mathcal Z\)-subsets
Cites Work
- Unnamed Item
- Improved limitedness theorems on finite automata with distance functions
- On measuring nondeterminism in regular languages
- Limitedness theorem on finite automata with distance functions
- Representation theorems on regular languages
- On the decidability of some problems about rational subsets of free partially commutative monoids
- On the topological structure of a finitely generated semigroup of matrices
- Multitape one-way nonwriting automata
- On the computational power of pushdown automata
- Regular languages of star height one
