iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/3-540-61440-0_139
New upper bounds to the limitedness of distance automata | SpringerLink
Skip to main content
Springer Nature Link
Log in

New upper bounds to the limitedness of distance automata

  • Session 7: Automata
  • Conference paper
  • First Online:
Automata, Languages and Programming (ICALP 1996)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1099))

Included in the following conference series:

Abstract

A distance automaton is a finite nondeterministic automaton with a distance function which assigns zero or one to each atomic transition and assigns a nonnegative integer to each accepted word by the plus-min principle. In this paper, we prove that the distances of all accepted words of a distance automaton is bounded by some constant if and only if they are bounded by 24m3 + m log(m + 2) + m, where m is the number of states of the automaton.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. K. Hashiguchi, Limitedness Theorem on finite automata with distance functions, J. Comput. System Sci. 24 (1982) 233–244.

    Google Scholar 

  2. K. Hashiguchi, Algorithms for determining relative star height and star height, Inform, and Control 78 (1988) 124–169.

    Google Scholar 

  3. K. Hashiguchi, Improved limitedness theorems on finite automata with distance functions, Theoret. Comput. Sci. 72 (1990) 27–38.

    Google Scholar 

  4. K. Hashiguchi, Algorithms for determining relative inclusion star height and inclusion star height, Theoret. Comput. Sci. 91 (1991) 85–100.

    Google Scholar 

  5. D. Krob, The equality problem for rational series with multiplicities in the tropical semiring is undecidable, In ternat, J. of Algebra and Computation 4 (1994) 405–425.

    Google Scholar 

  6. H. Leung, On the topological structure of a finitely generated semigroup of matrices, Semigroup Forum 37 (1988) 273–287.

    Google Scholar 

  7. I. Simon, Factorization forests of finite height, Theoret. Comput. Sci. 72 (1990) 65–94.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Information Technology, Faculty of Engineering, Okayama University, Tsushima, 700, Okayama, Japan

    Kosaburo Hashiguchi

Authors
  1. Kosaburo Hashiguchi
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Friedhelm Meyer Burkhard Monien

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Hashiguchi, K. (1996). New upper bounds to the limitedness of distance automata. In: Meyer, F., Monien, B. (eds) Automata, Languages and Programming. ICALP 1996. Lecture Notes in Computer Science, vol 1099. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61440-0_139

Download citation

  • DOI: https://doi.org/10.1007/3-540-61440-0_139

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-61440-1

  • Online ISBN: 978-3-540-68580-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation