Presentation	1994/10/21 On Read-k-times-only Branching Programs Yasuhiko Takenaga, Shuzo Yajima,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	We consider the computational power of branching programs under restrictions on the number of times to read each input.We define blockwise branching programs and compare them with the models with different restrictions on the order to read inputs.We prove some lower bounds and consider the relations between the classes represented by polynomial size branching programs.On read-twice- only models,we prove that the computational power is different according to the restrictions on the order to read inputs.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	branching program / Boolean function / lower bound
Paper #	COMP94-51
Date of Issue

Conference Information
Committee	COMP
Conference Date	1994/10/21(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	On Read-k-times-only Branching Programs
Sub Title (in English)
Keyword(1)	branching program
Keyword(2)	Boolean function
Keyword(3)	lower bound
1st Author's Name	Yasuhiko Takenaga
1st Author's Affiliation	Department of Information Science,Faculty of Engineering,Kyoto University()
2nd Author's Name	Shuzo Yajima
2nd Author's Affiliation	Department of Information Science,Faculty of Engineering,Kyoto University
Date	1994/10/21
Paper #	COMP94-51
Volume (vol)	vol.94
Number (no)	304
Page	pp.pp.-
#Pages	8
Date of Issue