[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

On a Class of Bijective Binary Transducers with Finitary Description Despite Infinite State Set

  • Conference paper
Implementation and Application of Automata (CIAA 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3845))

Included in the following conference series:

Abstract

We show that an infinite isometry f on {0,1}ω, i.e. computable by an infinite transducer T f , can be represented finitarily, provided the isometry [σ,f] := σ − 1 ∘ f − 1 ∘ σ ∘ f, the shift commutator of f, is finite, i.e. has a finite transducer T [σ,f]. We can describe all states of T f as words over Q [σ,f] and, using the nextstate and output functions of T [σ,f], obtain linear time algorithms for T f (in the length of the word in \(Q^*_{[ \sigma,f ]}\) describing the state in Q f ). The task of determining state equivalence within the first n input symbols or N=2n + 1-1 states is polynomial in the number N of states, if the shift commutator is finite.

Supported by FONDECYT 1040975, CONICYT. Partly supported by DID–UACh.

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

Similar content being viewed by others

References

  1. del Canales, M.P., Vielhaber, M.: Isometries of binary formal power series and their shift commutators. Electronic Colloq. on Comput. Compl. TR04–057 (2004)

    Google Scholar 

  2. Bouajjani, A., Jonsson, B., Nilsson, M., Touili, T.: Regular model checking. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, Springer, Heidelberg (2000)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Instituto de Matemáticas, Universidad Austral de Chile Casilla 567, Valdivia, Chile

    Michael Vielhaber & Mónica del Pilar Canales Ch.

Authors
  1. Michael Vielhaber
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mónica del Pilar Canales Ch.
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Sophia Antipolis, Laboratoire I3S, Les Algorithmes - bât. Euclide B, Université de Nice, 2000, route des lucioles, BP 121, 06903, Sophia Antipolis - Cedex, France

    Jacques Farré

  2. Sophia Antipolis, Ecole Polytechnique, Université de Nice, 930, route des colles, BP 145, 06903, Sophia Antipolis - Cedex, France

    Igor Litovsky

  3. Laboratoire I3S, Université de Nice, Sophia Antipolis & CNRS, France

    Sylvain Schmitz

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Vielhaber, M., del Pilar Canales Ch., M. (2006). On a Class of Bijective Binary Transducers with Finitary Description Despite Infinite State Set. In: Farré, J., Litovsky, I., Schmitz, S. (eds) Implementation and Application of Automata. CIAA 2005. Lecture Notes in Computer Science, vol 3845. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11605157_36

Download citation

  • DOI: https://doi.org/10.1007/11605157_36

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-31023-5

  • Online ISBN: 978-3-540-33097-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation