skip to main content
Language:
Search Limited to: Search Limited to: Resource type Show Results with: Show Results with: Search type Index

1-Bounded TWA Cannot Be Determinized

FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003, p.62-73 [Peer Reviewed Journal]

Springer-Verlag Berlin Heidelberg 2003 ;2004 INIST-CNRS ;ISSN: 0302-9743 ;ISBN: 9783540206804 ;ISBN: 3540206809 ;EISSN: 1611-3349 ;EISBN: 9783540245971 ;EISBN: 3540245979 ;DOI: 10.1007/978-3-540-24597-1_6

Full text available

Citations Cited by
  • Title:
    1-Bounded TWA Cannot Be Determinized
  • Author: BOJANCZYK, Mikołaj
  • Subjects: Applied sciences ; Computer science; control theory; systems ; Current Vertex ; Exact sciences and technology ; Previous Move ; Regular Language ; Theoretical computing ; Tree Automaton ; Tree Language
  • Is Part Of: FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003, p.62-73
  • Description: Tree-walking automata are a natural sequential model for recognizing tree languages which is closely connected to XML. Two long standing conjectures say TWA cannot recognize all regular languages and that deterministic TWA are weaker than nondeterministic TWA. We consider a weaker model, 1-TWA, of tree walking automata that can make only one pass through a tree. We show that deterministic 1-TWA are weaker than 1-TWA. We also show a very simple language not recognized by 1-TWA.
  • Publisher: Berlin, Heidelberg: Springer Berlin Heidelberg
  • Language: English
  • Identifier: ISSN: 0302-9743
    ISBN: 9783540206804
    ISBN: 3540206809
    EISSN: 1611-3349
    EISBN: 9783540245971
    EISBN: 3540245979
    DOI: 10.1007/978-3-540-24597-1_6
  • Source: Alma/SFX Local Collection
Back to results list
INSPIRE LIBRARY - TON DUC THANG UNIVERSITY (84-028) 37 755 057 Feedback
19 Nguyen Huu Tho St. Dist.7, HCM thuvien@tdtu.edu.vn

Copyright © 2017 INSPIRE LIBRARY - TON DUC THANG UNIVERSITY

Searching Remote Databases, Please Wait