Distance automata having large finite distance or finite ambiguity

DOI10.1007/BF01202281MaRDI QIDQ4032930zbMATH OpenFDO

Authors

Publication date 17 May 1993

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01202281

zbMATH Keywords

distance automaton

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 18646
• Approximate comparison of distance automata
• New upper bounds to the limitedness of distance automata
• A note on finitely ambiguous distance automata
• Approximate comparison of functions computed by distance automata

Cites work

• A decision procedure for the order of regular events
• Algorithms for determining relative star height and star height
• Amounts of nondeterminism in finite automata
• Finite automata having cost functions: Nondeterministic models
• scientific article; zbMATH DE number 3926250 (Why is no real title available?)
• scientific article; zbMATH DE number 4072419 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3767068 (Why is no real title available?)
• scientific article; zbMATH DE number 18646 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 459363 (Why is no real title available?)
• Improved limitedness theorems on finite automata with distance functions
• Limitedness theorem on finite automata with distance functions
• Limitedness theorem on finite automata with distance functions: An algebraic proof
• On finitely generated monoids of matrices with entries in $\mathbb {N}$
• On measuring nondeterminism in regular languages
• On the degree of ambiguity of finite automata
• On the relation between ambiguity and nondeterminism in finite automata
• Representation theorems on regular languages

Cited in

(14)

• A note on finitely ambiguous distance automata
• Finite-valued distance automata
• Exponential upper and lower bounds for the order of a regular language
• New upper bounds to the limitedness of distance automata
• Approximate comparison of functions computed by distance automata
• Approximate comparison of distance automata
• A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
• scientific article; zbMATH DE number 3926250 (Why is no real title available?)
• scientific article; zbMATH DE number 18646 (Why is no real title available?)
• scientific article; zbMATH DE number 2102758 (Why is no real title available?)
• Limited non-determinism hierarchy of counter automata
• Distance desert automata and the star height problem
• Limitedness theorem on finite automata with distance functions: An algebraic proof
• Bounded regular path queries in view-based data integration

This page was built for publication: Distance automata having large finite distance or finite ambiguity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4032930)