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)

zbMATH Keywords

distance automaton

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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

(13)

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

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)