Keyword : computational complexity


Low-Complexity Blind Spectrum Sensing in Alpha-Stable Distributed Noise Based on a Gaussian Function
Jinjun LUO Shilian WANG Eryang ZHANG 
Publication:   
Publication Date: 2019/07/01
Vol. E102-B  No. 7 ; pp. 1334-1344
Type of Manuscript:  PAPER
Category: Antennas and Propagation
Keyword: 
spectrum sensingimpulsive noisealpha stable distributionGaussian functioncomputational complexity
 Summary | Full Text:PDF

On-Off Power Control with Low Complexity in D2D Underlaid Cellular Networks
Tae-Won BAN Bang Chul JUNG 
Publication:   
Publication Date: 2018/09/01
Vol. E101-B  No. 9 ; pp. 1961-1966
Type of Manuscript:  PAPER
Category: Network
Keyword: 
D2D communicationsD2D underlaid cellular networkon-off power controlinterferencecomputational complexity
 Summary | Full Text:PDF

Computational Complexity and Polynomial Time Procedure of Response Property Problem in Workflow Nets
Muhammad Syafiq BIN AB MALEK Mohd Anuaruddin BIN AHMADON Shingo YAMAGUCHI 
Publication:   
Publication Date: 2018/06/01
Vol. E101-D  No. 6 ; pp. 1503-1510
Type of Manuscript:  Special Section PAPER (Special Section on Formal Approaches)
Category: Formal Approaches
Keyword: 
the response propertyPetri netprocess treecomputational complexitypolynomial time algorithm
 Summary | Full Text:PDF

A Computationally Efficient Leaky and Regularized RLS Filter for Its Short Length
Eisuke HORITA 
Publication:   
Publication Date: 2017/12/01
Vol. E100-A  No. 12 ; pp. 3045-3048
Type of Manuscript:  LETTER
Category: Digital Signal Processing
Keyword: 
adaptive filterRLScomputational complexityregularizationTikhonov
 Summary | Full Text:PDF

A Low Computational Complexity Algorithm for Compressive Wideband Spectrum Sensing
Shiyu REN Zhimin ZENG Caili GUO Xuekang SUN Kun SU 
Publication:   
Publication Date: 2017/01/01
Vol. E100-A  No. 1 ; pp. 294-300
Type of Manuscript:  LETTER
Category: Digital Signal Processing
Keyword: 
compressive wideband spectrum sensingaliased spectrumcoarse sensingfine sensingcomputational complexity
 Summary | Full Text:PDF

Comparing Performance of Hierarchical Identity-Based Signature Schemes
Peixin CHEN Yilun WU Jinshu SU Xiaofeng WANG 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2016/12/01
Vol. E99-D  No. 12 ; pp. 3181-3184
Type of Manuscript:  LETTER
Category: Information Network
Keyword: 
identity-based signaturecomputational complexityparing based cryptography
 Summary | Full Text:PDF

On the Computational Complexity of the Linear Solvability of Information Flow Problems with Hierarchy Constraint
Yuki TAKEDA Yuichi KAJI Minoru ITO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2016/12/01
Vol. E99-A  No. 12 ; pp. 2211-2217
Type of Manuscript:  Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Networks and Network Coding
Keyword: 
information flow problemnetwork codingcomputational complexityhierarchy constraintmesh network
 Summary | Full Text:PDF

Computational Complexity of Predicting Periodicity in the Models of Lorentz Lattice Gas Cellular Automata
Takeo HAGIWARA Tatsuie TSUKIJI Zhi-Zhong CHEN 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2016/06/01
Vol. E99-A  No. 6 ; pp. 1034-1049
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
cellular automatacomputational complexityLorentz lattice gasLangton's antPSPACE-complete
 Summary | Full Text:PDF

Fast Mode Decision Technique for HEVC Intra Prediction Based on Reliability Metric for Motion Vectors
Chihiro TSUTAKE Yutaka NAKANO Toshiyuki YOSHIDA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2016/04/01
Vol. E99-D  No. 4 ; pp. 1193-1201
Type of Manuscript:  PAPER
Category: Image Processing and Video Processing
Keyword: 
H.265/HEVCintra predictionmode decisionreliability metriccoding efficiencycomputational complexity
 Summary | Full Text:PDF

A Novel RZF Precoding Method Based on Matrix Decomposition: Reducing Complexity in Massive MIMO Systems
Qian DENG Li GUO Jiaru LIN Zhihui LIU 
Publication:   IEICE TRANSACTIONS on Communications
Publication Date: 2016/02/01
Vol. E99-B  No. 2 ; pp. 439-446
Type of Manuscript:  PAPER
Category: Antennas and Propagation
Keyword: 
massive MIMOmatrix decompositionRZF precodingcomputational complexitypower allocation
 Summary | Full Text:PDF

State Number Calculation Problem of Workflow Nets
Mohd Anuaruddin BIN AHMADON Shingo YAMAGUCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/06/01
Vol. E98-D  No. 6 ; pp. 1128-1136
Type of Manuscript:  Special Section PAPER (Special Section on Formal Approach)
Category: Petri net
Keyword: 
Petri netstate number calculation problemprocess treesolvabilitycomputational complexitymodel checking
 Summary | Full Text:PDF

Computational Complexity of Generalized Golf Solitaire
Chuzo IWAMOTO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/03/01
Vol. E98-D  No. 3 ; pp. 541-544
Type of Manuscript:  Special Section LETTER (Special Section on Foundations of Computer Science---New Spirits in Theory of Computation and Algorithm---)
Category: 
Keyword: 
computational complexityNP-completenesspuzzle
 Summary | Full Text:PDF

Candidate Boolean Functions towards Super-Quadratic Formula Size
Kenya UENO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/03/01
Vol. E98-D  No. 3 ; pp. 524-531
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science---New Spirits in Theory of Computation and Algorithm---)
Category: 
Keyword: 
Boolean functioncomputational complexityformula complexity
 Summary | Full Text:PDF

Computational Complexity of Generalized Forty Thieves
Chuzo IWAMOTO Yuta MATSUI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/02/01
Vol. E98-D  No. 2 ; pp. 429-432
Type of Manuscript:  LETTER
Category: Fundamentals of Information Systems
Keyword: 
computational complexityNP-completenesspuzzle
 Summary | Full Text:PDF

#P-hardness of Computing High Order Derivative and Its Logarithm
Ei ANDO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2014/06/01
Vol. E97-A  No. 6 ; pp. 1382-1384
Type of Manuscript:  Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
computable analysiscomputational complexity#P-hardnessSUBSET SUM
 Summary | Full Text:PDF

A Note on Cooperating Systems of One-Way Alternating Finite Automata with Only Universal States
Tatsuya FUJIMOTO Tsunehiro YOSHINAGA Makoto SAKAMOTO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2014/06/01
Vol. E97-A  No. 6 ; pp. 1375-1377
Type of Manuscript:  Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
cooperating system of one-way finite automataalternating finite automatauniversal statescomputational complexity
 Summary | Full Text:PDF

Generalized Pyramid is NP-Complete
Chuzo IWAMOTO Yuta MATSUI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2013/11/01
Vol. E96-D  No. 11 ; pp. 2462-2465
Type of Manuscript:  LETTER
Category: Fundamentals of Information Systems
Keyword: 
NP-completecomputational complexityone-player gamepyramid
 Summary | Full Text:PDF

Generalized Chat Noir is PSPACE-Complete
Chuzo IWAMOTO Yuta MUKAI Yuichi SUMIDA Kenichi MORITA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2013/03/01
Vol. E96-D  No. 3 ; pp. 502-505
Type of Manuscript:  Special Section LETTER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
Category: 
Keyword: 
PSPACE-completecomputational complexitytwo-player gameChat Noir
 Summary | Full Text:PDF

A Low Complexity H.264/AVC Deblocking Filter with Simplified Filtering Boundary Strength Decision
Luong Pham VAN Hoyoung LEE Jaehwan KIM Byeungwoo JEON 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2013/02/01
Vol. E96-A  No. 2 ; pp. 562-572
Type of Manuscript:  PAPER
Category: Digital Signal Processing
Keyword: 
deblocking filterH.264/AVCcomputational complexityhuman visual system
 Summary | Full Text:PDF

Generalized Shisen-Sho is NP-Complete
Chuzo IWAMOTO Yoshihiro WADA Kenichi MORITA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2012/11/01
Vol. E95-D  No. 11 ; pp. 2712-2715
Type of Manuscript:  LETTER
Category: Fundamentals of Information Systems
Keyword: 
NP-completecomputational complexityone-player gameShisen-Sho
 Summary | Full Text:PDF

An Efficient Conical Area Evolutionary Algorithm for Bi-objective Optimization
Weiqin YING Xing XU Yuxiang FENG Yu WU 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2012/08/01
Vol. E95-A  No. 8 ; pp. 1420-1425
Type of Manuscript:  LETTER
Category: Numerical Analysis and Optimization
Keyword: 
bi-objective optimizationevolutionary algorithmcomputational complexityconical arealocal Pareto optimality
 Summary | Full Text:PDF

Verifying Structurally Weakly Persistent Net Is Co-NP Complete
Atsushi OHTA Kohkichi TSUJI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2011/12/01
Vol. E94-A  No. 12 ; pp. 2832-2835
Type of Manuscript:  Special Section LETTER (Special Section on Mathematical Systems Science and its Applications)
Category: 
Keyword: 
concurrent systemPetri netsubclasscomputational complexity
 Summary | Full Text:PDF

Fast and Simple 2D Shape Retrieval Using Discrete Shock Graph
Solima KHANAM Seok-Woo JANG Woojin PAIK 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2011/10/01
Vol. E94-D  No. 10 ; pp. 2059-2062
Type of Manuscript:  LETTER
Category: Image Recognition, Computer Vision
Keyword: 
medial axesshock graphdeform costvisual transformationcomputational complexity
 Summary | Full Text:PDF

NP-Hard and k-EXPSPACE-Hard Cast Puzzles
Chuzo IWAMOTO Kento SASAKI Kenji NISHIO Kenichi MORITA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2010/11/01
Vol. E93-D  No. 11 ; pp. 2995-3004
Type of Manuscript:  PAPER
Category: Fundamentals of Information Systems
Keyword: 
computational complexityNP-hardk-EXPSPACE hardcast puzzle
 Summary | Full Text:PDF

Low-Complexity Fusion Estimation Algorithms for Multisensor Dynamic Systems
Seokhyoung LEE Vladimir SHIN 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2009/11/01
Vol. E92-A  No. 11 ; pp. 2910-2916
Type of Manuscript:  PAPER
Category: Communication Theory and Signals
Keyword: 
estimationKalman filteringfusion formulamultisensorCholesky factorizationcomputational complexity
 Summary | Full Text:PDF

Computational Complexity of Liveness Problem of Normal Petri Net
Atsushi OHTA Kohkichi TSUJI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2009/11/01
Vol. E92-A  No. 11 ; pp. 2717-2722
Type of Manuscript:  Special Section PAPER (Special Section on Theory of Concurrent Systems and its Applications)
Category: 
Keyword: 
concurrent systemPetri netlivenesscomputational complexity
 Summary | Full Text:PDF

Formal Language Theoretic Approach to the Disclosure Tree Strategy in Trust Negotiation
Yoshiaki TAKATA Hiroyuki SEKI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2009/02/01
Vol. E92-D  No. 2 ; pp. 200-210
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
trust managementtrust negotiationnegotiation strategycomputational complexitycontext-free grammar
 Summary | Full Text:PDF

Computational Complexities of University Interview Timetabling
Naoyuki KAMIYAMA Yuuki KIYONARI Eiji MIYANO Shuichi MIYAZAKI Katsuhisa YAMANAKA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2009/02/01
Vol. E92-D  No. 2 ; pp. 130-140
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
timetableschedulingoptimizationcomputational complexity
 Summary | Full Text:PDF

Performance Evaluation of MIMO-OFDM with Twin Turbo Decoder
Yasuyuki HATAKAWA Noriaki MIYAZAKI Toshinori SUZUKI 
Publication:   IEICE TRANSACTIONS on Communications
Publication Date: 2009/01/01
Vol. E92-B  No. 1 ; pp. 228-236
Type of Manuscript:  PAPER
Category: Wireless Communication Technologies
Keyword: 
iterative decodermultiple-input multiple-outputFEC (Forward Error Correction)correlated channelturbo codingcomputational complexity
 Summary | Full Text:PDF

Design of a Fuzzy Based Outer Loop Controller for Improving the Training Performance of LMS Algorithm
Ali OZEN Ismail KAYA Birol SOYSAL 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2008/12/01
Vol. E91-A  No. 12 ; pp. 3738-3744
Type of Manuscript:  Special Section PAPER (Special Section on Signal Design and its Applications in Communications)
Category: Channel Equalization
Keyword: 
channel equalizationtrackingfuzzy logic controllercomputational complexityconvergence of training
 Summary | Full Text:PDF

A Recursive Padding Technique on Nondeterministic Cellular Automata
Chuzo IWAMOTO Harumasa YONEDA Kenichi MORITA Katsunobu IMAI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2008/09/01
Vol. E91-A  No. 9 ; pp. 2335-2340
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
cellular automatacomputational complexityhierarchy theorem
 Summary | Full Text:PDF

Initial Codebook Algorithm of Vector Quantizaton
ShanXue CHEN FangWei LI WeiLe ZHU TianQi ZHANG 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2008/08/01
Vol. E91-D  No. 8 ; pp. 2189-2191
Type of Manuscript:  LETTER
Category: Algorithm Theory
Keyword: 
initialization methodcomputational complexityvector quantizationimage processing
 Summary | Full Text:PDF

A Delayed Estimation Filter Using Finite Observations on Delay Interval
HyongSoon KIM PyungSoo KIM SangKeun LEE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2008/08/01
Vol. E91-A  No. 8 ; pp. 2257-2262
Type of Manuscript:  LETTER
Category: Information Theory
Keyword: 
delayed estimationfixed-lag smoothingKalman filteringcomputational complexity
 Summary | Full Text:PDF

Fast Searching Algorithm for Vector Quantization Based on Subvector Technique
ShanXue CHEN FangWei LI WeiLe ZHU TianQi ZHANG 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2008/07/01
Vol. E91-D  No. 7 ; pp. 2035-2040
Type of Manuscript:  PAPER
Category: Image Processing and Video Processing
Keyword: 
encodingcomputational complexityvector quantizationdata compressionimage processing
 Summary | Full Text:PDF

Likelihood Estimation for Reduced-Complexity ML Detectors in a MIMO Spatial-Multiplexing System
Masatsugu HIGASHINAKA Katsuyuki MOTOYOSHI Akihiro OKAZAKI Takayuki NAGAYASU Hiroshi KUBO Akihiro SHIBUYA 
Publication:   IEICE TRANSACTIONS on Communications
Publication Date: 2008/03/01
Vol. E91-B  No. 3 ; pp. 837-847
Type of Manuscript:  PAPER
Category: Wireless Communication Technologies
Keyword: 
MIMOsphere decodingQRD-M algorithmsoft-decision outputscomputational complexity
 Summary | Full Text:PDF

Linearization of Loudspeaker Systems Using a Subband Parallel Cascade Volterra Filter
Hideyuki FURUHASHI Yoshinobu KAJIKAWA Yasuo NOMURA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2007/08/01
Vol. E90-A  No. 8 ; pp. 1616-1619
Type of Manuscript:  Special Section LETTER (Special Section on Papers Selected from the 21st Symposium on Signal Processing)
Category: 
Keyword: 
loudspeaker systemsnonlinear distortionVolterra kernelsubband parallel cascade realizationcomputational complexity
 Summary | Full Text:PDF

Low Complexity Encoding Based on Richardson's LDPC Codes
Hyunseuk YOO Chang Hui CHOE Moon Ho LEE 
Publication:   IEICE TRANSACTIONS on Communications
Publication Date: 2007/08/01
Vol. E90-B  No. 8 ; pp. 2151-2154
Type of Manuscript:  LETTER
Category: Fundamental Theories for Communications
Keyword: 
finite fieldscirculant permutation matricesRichardson's encoding schemecomputational complexity
 Summary | Full Text:PDF

Optimization Design of Biorthogonal Wavelets for Embedded Image Coding
Zaide LIU Nanning ZHENG Yuehu LIU Huub VAN DE WETERING 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2007/02/01
Vol. E90-D  No. 2 ; pp. 569-578
Type of Manuscript:  PAPER
Category: Image Processing and Video Processing
Keyword: 
biorthogonal waveletscoding gaincompression performancecomputational complexityDiophantine equationdiscrete wavelet transformfilter bank
 Summary | Full Text:PDF

Butterfly Structure for Viterbi Decoders of All Rates k/n
Tsung Sheng KUO Chau-Yun HSU 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2007/02/01
Vol. E90-A  No. 2 ; pp. 504-510
Type of Manuscript:  PAPER
Category: Coding Theory
Keyword: 
butterfly structureViterbi decoderconvolutional codescomputational complexity
 Summary | Full Text:PDF

A Co-channel Interference Cancellation Method Using Low Dimensional Sphere Decoding for MIMO Communication Systems
Masatsugu HIGASHINAKA Akihiro OKAZAKI Katsuyuki MOTOYOSHI Takayuki NAGAYASU Hiroshi KUBO Akihiro SHIBUYA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/10/01
Vol. E89-A  No. 10 ; pp. 2526-2534
Type of Manuscript:  Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Coding Theory
Keyword: 
MIMOsphere decodingco-channel interferencecomputational complexity
 Summary | Full Text:PDF

Decoding the (23, 12, 7) Golay Code Using a Low-Complexity Scheme
Ching-Lung CHR Szu-Lin SU Shao-Wei WU 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/08/01
Vol. E89-A  No. 8 ; pp. 2235-2238
Type of Manuscript:  LETTER
Category: Coding Theory
Keyword: 
(23127) binary Golay codealgebraic decoding schemestep-by-step decodingcomputational complexity
 Summary | Full Text:PDF

Computing Automorphism Groups of Chordal Graphs Whose Simplicial Components Are of Small Size
Seinosuke TODA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2006/08/01
Vol. E89-D  No. 8 ; pp. 2388-2401
Type of Manuscript:  INVITED PAPER (Special Section on Invited Papers from New Horizons in Computing)
Category: 
Keyword: 
chordal graphsimplicial componentautomorphismisomorphismcomputational group theoryalgorithmcomputational complexity
 Summary | Full Text:PDF

DWT Domain On-Line Signature Verification Using the Pen-Movement Vector
Isao NAKANISHI Hiroyuki SAKAMOTO Naoto NISHIGUCHI Yoshio ITOH Yutaka FUKUI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/04/01
Vol. E89-A  No. 4 ; pp. 1129-1131
Type of Manuscript:  LETTER
Category: Information Security
Keyword: 
on-line signature verificationDWTpen-movement vectorcomputational complexity
 Summary | Full Text:PDF

A Simple Step-by-Step Decoding of Binary BCH Codes
Ching-Lung CHR Szu-Lin SU Shao-Wei WU 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/08/01
Vol. E88-A  No. 8 ; pp. 2236-2239
Type of Manuscript:  LETTER
Category: Coding Theory
Keyword: 
BCH codestep-by-step decodingmatrix computationcomputational complexity
 Summary | Full Text:PDF

Computational and Memory Complexities of Greengard-Rokhlin's Fast Multipole Algorithm
Norimasa NAKASHIMA Mitsuo TATEIBA 
Publication:   IEICE TRANSACTIONS on Electronics
Publication Date: 2005/07/01
Vol. E88-C  No. 7 ; pp. 1516-1520
Type of Manuscript:  LETTER
Category: Electromagnetic Theory
Keyword: 
Greengard-Rokhlin's algorithmfast multipole methodcomputational complexitymemory complexity
 Summary | Full Text:PDF

A Subspace Blind Identification Algorithm with Reduced Computational Complexity--Colored Noise Case--
Nari TANABE Toshihiro FURUKAWA Kohichi SAKANIWA Shigeo TSUJII 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/07/01
Vol. E88-A  No. 7 ; pp. 2015-2018
Type of Manuscript:  LETTER
Category: Digital Signal Processing
Keyword: 
principal component analysissubspace methodcolored observation noisenoise variancechannel ordercomputational complexity
 Summary | Full Text:PDF

Strong Identification Based on a Hard-on-Average Problem
Pino CABALLERO-GIL 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/05/01
Vol. E88-A  No. 5 ; pp. 1117-1121
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
cryptographycomputational complexityalgorithmsdiscrete mathematics
 Summary | Full Text:PDF

Zero-Knowledge Proof for the Independent Set Problem
Pino CABALLERO-GIL 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/05/01
Vol. E88-A  No. 5 ; pp. 1301-1302
Type of Manuscript:  Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
cryptographycomputational complexityalgorithmsdiscrete mathematics
 Summary | Full Text:PDF

Finding Yozume of Generalized Tsume-Shogi is Exptime-Complete
Takayuki YATO Takahiro SETA Tsuyoshi ITO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/05/01
Vol. E88-A  No. 5 ; pp. 1249-1257
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
computational complexitygeneralized Tsume-Shogiyozumecombinatorial gamesanother solution problem
 Summary | Full Text:PDF

A Low-Complexity Step-by-Step Decoding Algorithm for Binary BCH Codes
Ching-Lung CHR Szu-Lin SU Shao-Wei WU 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/01/01
Vol. E88-A  No. 1 ; pp. 359-365
Type of Manuscript:  PAPER
Category: Coding Theory
Keyword: 
BCH codestep-by-step decodingmatrix computationcomputational complexity
 Summary | Full Text:PDF

A Practical Subspace Blind Identification Algorithm with Reduced Computational Complexity
Nari TANABE Toshihiro FURUKAWA Kohichi SAKANIWA Shigeo TSUJII 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2004/12/01
Vol. E87-A  No. 12 ; pp. 3360-3371
Type of Manuscript:  PAPER
Category: Digital Signal Processing
Keyword: 
principal component analysisautocorrelationsubspace methodeigenvalue and singular-value decompositioncomputational complexitychannel ordernoise variance
 Summary | Full Text:PDF

Efficient Codebook Search Method for AMR Wideband Speech Codecs
Hochong PARK Younhee KIM Jisang YOO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2004/08/01
Vol. E87-D  No. 8 ; pp. 2114-2120
Type of Manuscript:  PAPER
Category: Speech and Hearing
Keyword: 
AMR wideband codecACELPcodebook searchcomputational complexitypulse codevector
 Summary | Full Text:PDF

Reduction of Background Computations in Block-Matching Motion Estimation
Vasily G. MOSHNYAGA Koichi MASUNAGA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2004/03/01
Vol. E87-A  No. 3 ; pp. 539-546
Type of Manuscript:  Special Section PAPER (Special Section on Applications and Implementations of Digital Signal Processing)
Category: Video/Image Coding
Keyword: 
motion estimationvideo codingcomputational complexityhardware architectureadaptive processing
 Summary | Full Text:PDF

The Dynamic-Typed Access Matrix Model and Decidability of the Safety Problem
Masakazu SOSHI Mamoru MAEKAWA Eiji OKAMOTO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2004/01/01
Vol. E87-A  No. 1 ; pp. 190-203
Type of Manuscript:  Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Applications
Keyword: 
access controlaccess matrix modelsafety problemcomputational complexitydecidability
 Summary | Full Text:PDF

Complexity and Completeness of Finding Another Solution and Its Application to Puzzles
Takayuki YATO Takahiro SETA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/05/01
Vol. E86-A  No. 5 ; pp. 1052-1060
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
computational complexityNP-completeanother solutionpuzzle
 Summary | Full Text:PDF

Software Obfuscation on a Theoretical Basis and Its Implementation
Toshio OGISO Yusuke SAKABE Masakazu SOSHI Atsuko MIYAJI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/01/01
Vol. E86-A  No. 1 ; pp. 176-186
Type of Manuscript:  Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Protocols etc.
Keyword: 
tamper-resistant softwareobfuscationstatic analysiscomputational complexity
 Summary | Full Text:PDF

A Computation Reduced MMSE Adaptive Array Antenna Using Space-Temporal Simultaneous Processing Equalizer
Yoshihiro ICHIKAWA Koji TOMITSUKA Shigeki OBOTE Kenichi KAGOSHIMA 
Publication:   IEICE TRANSACTIONS on Communications
Publication Date: 2002/12/01
Vol. E85-B  No. 12 ; pp. 2622-2629
Type of Manuscript:  Special Section PAPER (Special Issue on Software Defined Radio Technology and Its Applications)
Category: 
Keyword: 
adaptive array antennaMMSEcomputational complexityspace-temporal simultaneous processing equalizer
 Summary | Full Text:PDF

NP-Hardness of Liveness Problem of Bounded Asymmetric Choice Net
Atsushi OHTA Kohkichi TSUJI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2002/05/01
Vol. E85-A  No. 5 ; pp. 1071-1074
Type of Manuscript:  Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
concurrent systemPetri netlivenesscomputational complexity
 Summary | Full Text:PDF

On Cellular Arrays and Other Topics in Parallel Computing
Oscar H. IBARRA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2002/02/01
Vol. E85-D  No. 2 ; pp. 312-321
Type of Manuscript:  INVITED SURVEY PAPER
Category: 
Keyword: 
cellular arraycomputational complexityparallel complexityreachabilitycommutativity analysis
 Summary | Full Text:PDF

A Note on Realtime One-Way Alternating and Deterministic Multi-Counter Automata
Tsunehiro YOSHINAGA Katsushi INOUE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2002/02/01
Vol. E85-D  No. 2 ; pp. 346-349
Type of Manuscript:  Special Section LETTER (Special Issue on Selected Papers from LA Symposium)
Category: 
Keyword: 
alternating multi-counter automatadeterministic multi-counter automataone-way computationrealtime computationcomputational complexity
 Summary | Full Text:PDF

Polynomial Time Decidability of Monotone Liveness of Time Bounded AC/DC Nets
Atsushi OHTA Kohkichi TSUJI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2001/11/01
Vol. E84-A  No. 11 ; pp. 2865-2870
Type of Manuscript:  Special Section PAPER (Special Section on Concurrent Systems Technology)
Category: 
Keyword: 
concurrent systemPetri netlivenesscomputational complexity
 Summary | Full Text:PDF

On the Complexity of Constructing an Elliptic Curve of a Given Order
Masato YAMAMICHI Masahiro MAMBO Hiroki SHIZUYA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2001/01/01
Vol. E84-A  No. 1 ; pp. 140-145
Type of Manuscript:  Special Section PAPER (Special Section on Cryptography and Information Security)
Category: 
Keyword: 
elliptic curvefunction classcomputational complexity
 Summary | Full Text:PDF

Computational Complexity of Finding Highly Co-occurrent Itemsets in Market Basket Databases
Yeon-Dae KWON Yasunori ISHIHARA Shougo SHIMIZU Minoru ITO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/12/25
Vol. E83-A  No. 12 ; pp. 2723-2735
Type of Manuscript:  PAPER
Category: General Fundamentals and Boundaries
Keyword: 
data mininglarge itemsethighly co-occurrent itemsetcomputational complexity
 Summary | Full Text:PDF

The Optimal Sectionalized Trellises for the Generalized Version of Viterbi Algorithm of Linear Block Codes and Its Application to Reed-Muller Codes
Yuansheng TANG Toru FUJIWARA Tadao KASAMI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/11/25
Vol. E83-A  No. 11 ; pp. 2329-2340
Type of Manuscript:  PAPER
Category: Coding Theory
Keyword: 
linear block codesectionalizationminimal sectionalized trellisgeneralized Viterbi algorithmcomputational complexity
 Summary | Full Text:PDF

NP-Completeness of Reallocation Problems with Restricted Block Volume
Hiroyoshi MIWA Hiro ITO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/04/25
Vol. E83-A  No. 4 ; pp. 590-597
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
reallocationcomputational complexityNP-completeSATsteiner tree problem
 Summary | Full Text:PDF

NP-Hardness of Rotation Type Cell-Mazes
Shiro AOKI Hiro ITO Hideyuki UEHARA Mitsuo YOKOYAMA Tsuyoshi HORINOUCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/03/25
Vol. E83-A  No. 3 ; pp. 492-496
Type of Manuscript:  Special Section LETTER (Special Section of Selected Papers from the 12th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
puzzlemazecomputational complexityNP-hardpolynomial-time
 Summary | Full Text:PDF

Computational Complexity of Finding Meaningful Association Rules
Yeon-Dae KWON Ryuichi NAKANISHI Minoru ITO Michio NAKANISHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1999/09/25
Vol. E82-A  No. 9 ; pp. 1945-1952
Type of Manuscript:  PAPER
Category: Algorithms and Data Structures
Keyword: 
data mininglarge itemsetmeaningful association rulecomputational complexitydatabase
 Summary | Full Text:PDF

On Complexity of Computing the Permanent of a Rectangular Matrix
Tsutomu KAWABATA Jun TARUI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1999/05/25
Vol. E82-A  No. 5 ; pp. 741-744
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
permanentcomputational complexitydifferential operator on circuits
 Summary | Full Text:PDF

Computationally Efficient Bicomplex Multipliers for Digital Signal Processing
Hisamichi TOYOSHIMA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1998/02/25
Vol. E81-D  No. 2 ; pp. 236-238
Type of Manuscript:  LETTER
Category: Algorithm and Computational Complexity
Keyword: 
computational complexityhypercomplex numberbicomplex multiplierdigital signal processing
 Summary | Full Text:PDF

A Note on the Complexity of k-Ary Threshold Circuits
Shao-Chin SUNG Kunihiko HIRAISHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1997/08/25
Vol. E80-D  No. 8 ; pp. 767-773
Type of Manuscript:  PAPER
Category: Algorithm and Computational Complexity
Keyword: 
computational complexitythreshold circuitsymmetric function
 Summary | Full Text:PDF

Syntactic Unification Problems under Constrained Substitutions
Kazuhiro TAKADA Yuichi KAJI Tadao KASAMI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1997/05/25
Vol. E80-D  No. 5 ; pp. 553-561
Type of Manuscript:  PAPER
Category: Automata,Languages and Theory of Computing
Keyword: 
unification problemdecidabilitycomputational complexityorder-sorted signaturetree automata
 Summary | Full Text:PDF

Computational Power of Nondeterministic Ordered Binary Decision Diagrams and Their Subclasses
Kazuyoshi TAKAGI Koyo NITTA Hironori BOUNO Yasuhiko TAKENAGA Shuzo YAJIMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1997/04/25
Vol. E80-A  No. 4 ; pp. 663-669
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
computational complexityBoolean functionordered binary decision diagramsatisfiabilitycombinational circuitcutwidthsum-of-product formzero-suppressed binary decision diagrams (BDD)ternary decision diagram
 Summary | Full Text:PDF

Computing the Minkowski Sum of Monotone Polygons
Antonio HERNAN'DEZ-BARRERA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1997/02/25
Vol. E80-D  No. 2 ; pp. 218-222
Type of Manuscript:  PAPER
Category: Algorithm and Computational Complexity
Keyword: 
algorithmscomputational complexitycomputational geometryMinkowski summonotone polygonlower envelope
 Summary | Full Text:PDF

The Complexity of Threshold Circuits for Parity Functions
Shao-Chin SUNG Tetsuro NISHINO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1997/01/25
Vol. E80-D  No. 1 ; pp. 91-93
Type of Manuscript:  LETTER
Category: Algorithm and Computational Complexity
Keyword: 
computational complexitythreshold circuitparity function
 Summary | Full Text:PDF

A Relationship between the Number of Negations and the Circuit Size
Keisuke TANAKA Tetsuro NISHINO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1996/09/25
Vol. E79-D  No. 9 ; pp. 1355-1357
Type of Manuscript:  LETTER
Category: Algorithm and Computational Complexity
Keyword: 
computational complexitytheory of computation
 Summary | Full Text:PDF

Digital Halftoning Algorithms Based on Optimization Criteria and Their Experimental Evaluation
Tetsuo ASANO Desh RANJAN Thomas ROOS 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/04/25
Vol. E79-A  No. 4 ; pp. 524-532
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
discrete algorithmcombinatiorial optimizationdigital halftoningcomputational complexityexperimental evaluation
 Summary | Full Text:PDF

A Fast and Accurate Algorithm for Computing Desired Eigenpairs of Hermitian Matrices
Chang Wan JEON Hyoung Joong KIM Jang Gyu LEE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1996/03/25
Vol. E79-D  No. 3 ; pp. 182-188
Type of Manuscript:  PAPER
Category: Algorithm and Computational Complexity
Keyword: 
eigenvalueeigenvectoralgorithmcomputational complexity
 Summary | Full Text:PDF

On the Complexity of the Discrete Logarithm for a General Finite Group
Tatsuaki OKAMOTO Kouichi SAKURAI Hiroki SHIZUYA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/01/25
Vol. E79-A  No. 1 ; pp. 61-65
Type of Manuscript:  Special Section PAPER (Special Section on Cryptography and Information Security)
Category: 
Keyword: 
discrete logarithmcomputational complexitycryptography
 Summary | Full Text:PDF

A Priori Estimation of Newton Type Homotopy Method for Calculating an Optimal Solution of Convex Optimization Problem
Mitsunori MAKINO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1995/10/25
Vol. E78-A  No. 10 ; pp. 1339-1344
Type of Manuscript:  Special Section PAPER (Special Section on Nonlinear Theory and Its Applications)
Category: 
Keyword: 
homotopy methodconvex programmingnonlinear programmingcomputational complexitymonotone operatornonlinear system analysis
 Summary | Full Text:PDF

A Mathematical Solution to a Network Designing Problem
Yoshikane TAKAHASHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1995/10/25
Vol. E78-A  No. 10 ; pp. 1381-1411
Type of Manuscript:  PAPER
Category: Neural Networks
Keyword: 
neural networksnetwork designingnetwork trainingminimum intermediate unitscomputational complexityrate distortion theorylinear algebra
 Summary | Full Text:PDF

Alternating Finite Automata with Counters and Stack-Counters Operating in Realtime
Tsunehiro YOSHINAGA Katsushi INOUE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1995/08/25
Vol. E78-D  No. 8 ; pp. 929-938
Type of Manuscript:  PAPER
Category: Automata, Languages and Theory of Computing
Keyword: 
alternationrealtime computationone-way counter automataone-way stack-counter automatacomputational complexity
 Summary | Full Text:PDF

Learning Theory Toward Genome Informatics
Satoru MIYANO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1995/05/25
Vol. E78-D  No. 5 ; pp. 560-567
Type of Manuscript:  Special Section PAPER (Special Issue on Algorithmic Learning Theory)
Category: Machine Learning and Its Applications
Keyword: 
PAC-learningcomputational complexityknowledge acquisitiongenome informaics
 Summary | Full Text:PDF

On the Number of Negations Needed to Compute Parity Functions
Tetsuro NISHINO Jaikumar RADHAKRISHNAN 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1995/01/25
Vol. E78-D  No. 1 ; pp. 90-91
Type of Manuscript:  LETTER
Category: Algorithm and Computational Complexity
Keyword: 
computational complexityboolean circuitparity function
 Summary | Full Text:PDF

On the Negation-Limited Circuit Complexity of Clique Functions
Tetsuro NISHINO Keisuke TANAKA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1995/01/25
Vol. E78-D  No. 1 ; pp. 86-89
Type of Manuscript:  LETTER
Category: Algorithm and Computational Complexity
Keyword: 
computational complexityboolean circuitclique function
 Summary | Full Text:PDF

Finite State Translation Systems and Parallel Multiple Context-Free Grammars
Yuichi KAJI Hiroyuki SEKI Tadao KASAMI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1994/06/25
Vol. E77-D  No. 6 ; pp. 619-630
Type of Manuscript:  PAPER
Category: Automata, Languages and Theory of Computing
Keyword: 
finite state translation systemsparallel multiple context-free grammarstree automatacomputational complexityformal languages
 Summary | Full Text:PDF

On the Complexity of Protocol Validation Problems for Protocols with Bounded Capacity Channels
Yoshiaki KAKUDA Yoshihiro TAKADA Tohru KIKUNO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1994/04/25
Vol. E77-A  No. 4 ; pp. 658-667
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
computational complexitydeadlockNP-completeprotocolprotocol validation
 Summary | Full Text:PDF

Hierarchical Properties of Realtime One-Way Alternating Multi-Stack-Counter Automata
Tsunehiro YOSHINAGA Katsushi INOUE Itsuo TAKANAMI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1994/04/25
Vol. E77-A  No. 4 ; pp. 621-629
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
alternating automataone-way counterone-way stack-countercomputational complexity
 Summary | Full Text:PDF

A Note on One-Way Multicounter Machines and Cooperating Systems of One-Way Finite Automata
Yue WANG Katsushi INOUE Itsuo TAKANAMI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1993/10/25
Vol. E76-D  No. 10 ; pp. 1302-1306
Type of Manuscript:  LETTER
Category: Automaton, Language and Theory of Computing
Keyword: 
one-way multicounter automatacooperating systems of one-way finite automatahierarchycomputational complexity
 Summary | Full Text:PDF

Some Hierarchy Results on Multihead Automata over a One-Letter Alphabet
Yue WANG Katsushi INOUE Itsuo TAKANAMI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1993/06/25
Vol. E76-D  No. 6 ; pp. 625-633
Type of Manuscript:  PAPER
Category: Automaton, Language and Theory of Computing
Keyword: 
sensing multihead automataautomata on two-dimensional tapesone-letter alphabethierarchycomputational complexity
 Summary | Full Text:PDF

A Sufficient Condition of A Priori Estimation for Computational Complexity of the Homotopy Method
Mitsunori MAKINO Masahide KASHIWAGI Shin'ichi OISHI Kazuo HORIUCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1993/05/25
Vol. E76-A  No. 5 ; pp. 786-794
Type of Manuscript:  Special Section PAPER (Special Section on Neural Nets,Chaos and Numerics)
Category: Numerical Homotopy Method and Self-Validating Numerics
Keyword: 
numerical methodsnonliner system analysishomotopy methodcomputational complexitymonotone operator
 Summary | Full Text:PDF

A Linear Time Algorithm for Smallest Augmentation to 3-Edge-Connect a Graph
Toshimasa WATANABE Mitsuhiro YAMAKADO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1993/04/25
Vol. E76-A  No. 4 ; pp. 518-531
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
linear-time algorithms3-edge-connected graphsconnectivity augmentationcomputational complexity
 Summary | Full Text:PDF

Some EXPTIME Complete Problems on Context-Free Languages
Takumi KASAI Shigeki IWATA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1993/03/25
Vol. E76-D  No. 3 ; pp. 329-335
Type of Manuscript:  PAPER
Category: Algorithm and Computational Complexity
Keyword: 
computational complexityEXPTIME completecontext-free languagepebble game problem
 Summary | Full Text:PDF

The Universal Recognition Problems for Parallel Multiple Context-Free Grammars and for Their Subclasses
Yuichi KAJI Ryuichi NAKANISHI Hiroyuki SEKI Tadao KASAMI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1992/07/25
Vol. E75-D  No. 4 ; pp. 499-508
Type of Manuscript:  PAPER
Category: Automaton, Language and Theory of Computing
Keyword: 
parallel multiple context-free grammarsuniversal recognition problemcomputational complexityformal language
 Summary | Full Text:PDF

The Universal Recognition Problems for Multiple Context-Free Grammars and for Linear Context-Free Rewriting Systems
Yuichi KAJI Ryuichi NAKANISI Hiroyuki SEKI Tadao KASAMI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1992/01/25
Vol. E75-D  No. 1 ; pp. 78-88
Type of Manuscript:  Special Section PAPER (Special Section on Theoretical Foundations of Computing)
Category: 
Keyword: 
multiple context-free grammarsrecognition problemcomputational complexityformal language
 Summary | Full Text:PDF