检索结果-内蒙古大学图书馆

size complexity of rotating and sweeping automata

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2012年第2期78卷 537-558页

作者： Kapoutsis, Christos Kralovic, Richard Moemke, Tobias Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland

We examine the succinctness of one-way, rotating, sweeping, and two-way deterministic finite automata (1DFAs, RDFAs, SDFAs, 2DFAs) and their nondeterministic and randomized counterparts. Here, a SDFA is a 2DFA whose head can change direction only on the end-markers and a RDFA is a SDFA whose head is reset to the left end of the input every time the right end-marker is read. We study the size complexity classes defined by these automata, i.e., the classes of problems solvable by small automata of certain type. For any pair of classes of one-way, rotating, and sweeping deterministic (1D, RD, SD), self-verifying (1 Delta, R Delta, S Delta) and nondeterministic (1N, RN, SN) automata, as well as for their complements and reversals, we show that they are equal, incomparable, or one is strictly included in the other. The provided map of the complexity classes has interesting implications on the power of randomization for finite automata. Among other results, it implies that Las Vegas sweeping automata can be exponentially more succinct than SDFAs. We introduce a list of language operators and study the corresponding closure properties of the size complexity classes defined by these automata as well. Our conclusions reveal also the logical structure of certain proofs of known separations among the complexity classes and allow us to systematically construct alternative witnesses of these separations. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Finite automata Sweeping automata size complexity Self-verification Randomization Hardness propagation

来源：评论

学校读者我要写书评

暂无评论

A Logical Characterization of Small 2NFAs 21st

A Logical Characterization of Small 2NFAs

引用

21st International Conference on Implementation and Application of Automata (CIAA)

作者： Kapoutsis, Christos A. Mulaffer, Lamana Carnegie Mellon Univ POB 24866 Doha Qatar Texas A&M Univ POB 23874 Doha Qatar

ISBN: (纸本)9783319409450

Let 2N be the class of families of problems solvable by families of two-way nondeterministic finite automata of polynomial size. We characterize 2N in terms of families of formulas of transitive-closure logic. These formulas apply the transitive-closure operator on a quantifier-free disjunctive normal form of first-order logic with successor and constants, where (i) apart from two special variables, all others are equated to constants in every clause, and (ii) no clause simultaneously relates these two special variables and refers to fixed input cells. We prove that automata with polynomially many states are as powerful as formulas with polynomially many clauses and polynomially large constants. This can be seen as a refinement of Immermans theorem that nondeterministic logarithmic space matches positive transitive-closure logic (NL = FO + pos TC).

关键词： size complexity two-way finite automata nondeterminism descriptive complexity descriptional complexity minicomplexity

来源：评论

学校读者我要写书评

暂无评论

A Logical Characterization of Small 2NFAs

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2017年第5期28卷 445-464页

作者： Kapoutsis, Christos A. Mulaffer, Lamana Carnegie Mellon Univ POB 24866 Doha Qatar Texas A&M Univ POB 23874 Doha Qatar

关键词： size complexity two-way finite automata nondeterminism descriptive complexity descriptional complexity minicomplexity

来源：评论

学校读者我要写书评

暂无评论

Infinite vs. finite size-bounded randomized computations

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2014年第4期80卷 744-765页

作者： Kralovic, Richard Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland Google Zurich Zurich Switzerland

Randomized computations can be very powerful with respect to space complexity, e.g., for logarithmic space, LasVegas is equivalent to nondeterminism. This power depends on the possibility of infinite computations, however, it is an open question if they are necessary. We answer this question for rotating finite automata (RFAs) and sweeping finite automata (sFAs). We show that LasVegas RMS (SPAS) allowing infinite computations, although only with probability 0, can be exponentially smaller than LasVegas RFAS (SFAS) forbidding them. In particular, we show that even RFAS (SFAS) with linear expected running time may require exponentially more states than RFAS (SFAS) running in exponential time. We also strengthen this result, showing that the restriction on time cannot be traded for the more powerful bounded-error randomization. To prove our results, we introduce a technique for proving lower bounds on size of RFAS (SFAS) that generalizes the notion of generic strings discovered by M. Sipser. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Probabilistic computations Las Vegas randomization Time complexity size complexity Rotating finite automata Sweeping finite automata

来源：评论

学校读者我要写书评

暂无评论

Mathematical modelling and a meta-heuristic for flexible job shop scheduling

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2013年第20期51卷 6247-6274页

作者： Roshanaei, V. Azab, Ahmed ElMaraghy, H. Univ Windsor Intelligent Mfg Syst IMS Ctr Windsor ON N9B 3P4 Canada

This study develops new solution methodologies for the flexible job shop scheduling problem (F-JSSP). As a first step towards dealing with this complex problem, mathematical modellings have been used;two novel effective position- and sequence-based mixed integer linear programming (MILP) models have been developed to fully characterise operations of the shop floor. The developed MILP models are capable of solving both partially and totally F-JSSPs. size complexities, solution effectiveness and computational efficiencies of the developed MILPs are numerically explored and comprehensively compared vis-a-vis the makespan optimisation criterion. The acquired results demonstrate that the proposed MILPs, by virtue of its structural efficiencies, outperform the state-of-the-art MILPs in literature. The F-JSSP is strongly NP-hard;hence, it renders even the developed enhanced MILPs inefficient in generating schedules with the desired quality for industrial scale problems. Thus, a meta-heuristic that is a hybrid of Artificial Immune and Simulated Annealing (AISA) Algorithms has been proposed and developed for larger instances of the F-JSSP. Optimality gap is measured through comparison of AISA's suboptimal solutions with its MILP exact optimal counterparts obtained for small- to medium-size benchmarks of F-JSSP. The AISA's results were examined further by comparing them with seven of the best-performing meta-heuristics applied to the same benchmark. The performed comparative analysis demonstrated the superiority of the developed AISA algorithm. An industrial problem in a mould- and die-making shop was used for verification.

关键词： scheduling flexible job shop mixed integer linear programming hybrid artificial immune algorithms simulated annealing size complexity optimality gap

来源：评论

学校读者我要写书评

暂无评论

On the size complexity of hybrid networks of evolutionary processors

引用

THEORETICAL COMPUTER SCIENCE 2005年第2期330卷 205-220页

作者： Castellanos, J Leupold, P Mitrana, V Univ Bucharest Fac Math & Comp Sci Bucharest 70109 Romania Univ Politecn Madrid Dept Artificial Intelligence E-28660 Madrid Spain Univ Rovira & Virgili Res Grp Math Linguist Tarragona 43005 Spain

The goal of this paper is twofold. Firstly, to survey in a systematic and uniform way the main results regarding the size descriptional complexity measures of hybrid networks of evolutionary processors as generating devices. Secondly, we improve some results about a size measure, prove that it is connected, and discuss the possibility of computing this measure for regular and context-free languages. We also briefly present a few NP-complete problems and recall how they can be solved in linear time by accepting networks of evolutionary processors with linearly bounded resources (nodes, rules, symbols). Finally, the size complexity of accepting hybrid networks of evolutionary processors recognizing all NP languages in polynomial time is briefly discussed. (C) 2004 Elsevier B.V. All rights reserved.

关键词： evolutionary operations evolutionary processor hybrid network of evolutionary processors size complexity connectivity

来源：评论

学校读者我要写书评

暂无评论

On the size complexity of hybrid networks of evolutionary processors

On the size complexity of hybrid networks of evolutionary pr...

引用

Workshop on Descriptional complexity of Formal Systems

关键词： evolutionary operations evolutionary processor hybrid network of evolutionary processors size complexity connectivity

来源：评论

学校读者我要写书评

暂无评论

Computational completeness of hybrid networks of evolutionary processors with seven nodes

Computational completeness of hybrid networks of evolutionar...

引用

10th International Workshop on Descriptional complexity of Formal Systems, DCFS 2008

作者： Alhazov, Artiom Csuhaj-Varj´u, Erzśebet Mart´in-Vide, Carlos Rogozhin, Yurii Institute of Mathematics and Computer Science Academy of Sciences of Moldova Academiei 5 MD-2028 Chisinau Moldova Computer and Automation Research Institute Hungarian Academy of Sciences Kende u. 13-17 1111 Budapest Hungary Department of Algorithms and their Applications Faculty of Informatics Ëotvos Loŕand University Pazmany Peter sétány 1/c H-1117 Budapest Hungary Research Group on Mathematical Linguistics Rovira I Virgili University Pl. Imperial Tàrraco 1 43005 Tarragona Spain

ISBN: (纸本)9780919013568

A hybrid network of evolutionary processors (an HNEP) is a graph where each node is associated with a language processor (an evolutionary processor), a set of words, an input filter and an output filter. The evolutionary processor performs one type of point mutations (insertion, deletion or substitution) on the words in that node. The filters are defined by certain variants of random-context conditions. In this paper, by improving our previous result, we prove that HNEPs with 7 nodes are able to generate any recursively enumerable language. We also show that the family of HNEPs with 2 nodes is not computationally complete.

关键词： Hybrid networks of evolutionary processors size complexity Small universal systems

来源：评论

学校读者我要写书评

暂无评论

On small universal antiport P systems

引用

THEORETICAL COMPUTER SCIENCE 2007年第2-3期372卷 152-164页

作者： Csuhaj-Varju, Erzsebet Margenstern, Maurice Vaszil, Gyorgy Verlan, Sergey Hungarian Acad Sci Comp & Automat Res Inst H-1111 Budapest Hungary Univ Paul Verlaine Metz LITA EA 3097 F-57045 Metz 1 France Univ Paris 12 LACL UFR Sci & Technol F-94010 Creteil France

It is known that P systems with antiport rules simulate register machines, i.e., they are computationally complete. Hence, due to the existence of universal register machines, there exist computationally complete subclasses of antiport P systems with bounded size, i.e., systems where each size parameter is limited by some constant. However, so far there has been no estimation of these numbers given in the literature. In this article, three universal antiport P systems of bounded size are demonstrated, different from each other in their size parameters. We present universal antiport P systems with 73, 43, and 30 rules where the maximum of the weight of the rules is 4, 5, and 6, respectively. (c) 2006 Elsevier B.V. All rights reserved.

关键词： P systems universality size complexity

来源：评论

学校读者我要写书评

暂无评论

Parallel communicating grammar systems with bounded resources

引用

THEORETICAL COMPUTER SCIENCE 2002年第1-2期276卷 205-219页

作者： Csuhaj-Varjú, E Vaszil, G Hungarian Acad Sci Comp & Automat Res Inst H-1111 Budapest Hungary

In this paper we study size properties of context-free returning parallel communicating grammar systems (PC grammar systems). We show that for each context-free returning PC grammar system an equivalent system of this type can be constructed, where the total number of symbols used for describing a component can be bounded by a reasonably small constant. Since context-free returning PC grammar systems determine the class of recursively enumerable languages, the result also demonstrates that the recursively enumerable language class can be economically described in terms of parallel communicating grammar systems. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： grammar systems size complexity recursively enumerable languages

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：