Distance automata having large finite distance or finite ambiguity

DOI10.1007/BF01202281zbMATH Open0771.68088MaRDI QIDQ4032930FDOQ4032930

Authors:

Publication date: 17 May 1993

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

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

zbMATH Keywords

distance automaton

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Amounts of nondeterminism in finite automata
• Title not available (Why is that?)
• Limitedness theorem on finite automata with distance functions
• Representation theorems on regular languages
• Improved limitedness theorems on finite automata with distance functions
• On the relation between ambiguity and nondeterminism in finite automata
• Algorithms for determining relative star height and star height
• On the degree of ambiguity of finite automata
• On measuring nondeterminism in regular languages
• Title not available (Why is that?)
• Limitedness theorem on finite automata with distance functions: An algebraic proof
• A decision procedure for the order of regular events
• Title not available (Why is that?)
• On finitely generated monoids of matrices with entries in $\mathbb {N}$
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finite automata having cost functions: Nondeterministic models

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
• Distance desert automata and the star height problem
• Finite-valued distance automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)