Oscar H. Ibarra

According to our database1, Oscar H. Ibarra
  • authored at least 374 papers between 1967 and 2017.
  • has a "Dijkstra number"2 of three.

Awards

ACM Fellow

ACM Fellow 1995, "For contributions to the design and analysis of algorithms, the theory of computation, computational complexity, and parallel computing.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
On the overlap assembly of strings and languages.
Natural Computing, 2017

Deletion operations on deterministic families of automata.
Inf. Comput., 2017

Further remarks on DNA overlap assembly.
Inf. Comput., 2017

Information rate of some classes of non-regular languages: An automata-theoretic approach.
Inf. Comput., 2017

Variations of Checking Stack Automata: Obtaining Unexpected Decidability Properties.
CoRR, 2017

On Store Languages of Language Acceptors.
CoRR, 2017

Lossiness of communication channels modeled by transducers.
Computability, 2017

On Finite-Index Indexed Grammars and Their Restrictions.
Proceedings of the Language and Automata Theory and Applications, 2017

Introduction to APDCM Workshop.
Proceedings of the 2017 IEEE International Parallel and Distributed Processing Symposium Workshops, 2017

Variations of Checking Stack Automata: Obtaining Unexpected Decidability Properties.
Proceedings of the Developments in Language Theory - 21st International Conference, 2017

2016
The effect of end-markers on counter machines and commutativity.
Theor. Comput. Sci., 2016

Quantifying communication in synchronized languages.
Theor. Comput. Sci., 2016

Preface.
Natural Computing, 2016

On decidability and closure properties of language classes with respect to bio-operations.
Natural Computing, 2016

Announcement.
Int. J. Found. Comput. Sci., 2016

On bounded languages and reversal-bounded automata.
Inf. Comput., 2016

Execution information rate for some classes of automata.
Inf. Comput., 2016

Visibly Pushdown Automata and Transducers with Counters.
Fundam. Inform., 2016

Deletion Operations on Deterministic Families of Automata.
CoRR, 2016

On the Complexity and Decidability of Some Problems Involving Shuffle.
CoRR, 2016

On Finite-Index Indexed Grammars and Their Restrictions.
CoRR, 2016

On Bounded Semilinear Languages, Counter Machines, and Finite-Index ET0L.
Proceedings of the Implementation and Application of Automata, 2016

APDCM Introduction and Committees.
Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium Workshops, 2016

On Families of Full Trios Containing Counter Machine Languages.
Proceedings of the Developments in Language Theory - 20th International Conference, 2016

2015
Alberto Apostolico.
Int. J. Found. Comput. Sci., 2015

On the Ambiguity and Finite-Valuedness Problems in Acceptors and Transducers.
Int. J. Found. Comput. Sci., 2015

Semilinear Sets and Counter Machines: a Brief Survey.
Fundam. Inform., 2015

Deletion Operations on Deterministic Families of Automata.
Proceedings of the Theory and Applications of Models of Computation, 2015

Insertion Operations on Deterministic Reversal-Bounded Counter Machines.
Proceedings of the Language and Automata Theory and Applications, 2015

APDCM Introduction and Committees.
Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium Workshop, 2015

On the Density of Context-Free and Counter Languages.
Proceedings of the Developments in Language Theory - 19th International Conference, 2015

On the Complexity and Decidability of Some Problems Involving Shuffle.
Proceedings of the Descriptional Complexity of Formal Systems, 2015

Quantifying Communication in Synchronized Languages.
Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

2014
Weak Synchronization and Synchronizability of Multi-tape Pushdown Automata and Turing Machines.
Journal of Automata, Languages and Combinatorics, 2014

Some Decision Questions Concerning the Time Complexity of Language Acceptors.
Int. J. Found. Comput. Sci., 2014

Automata-based symbolic string analysis for vulnerability detection.
Formal Methods in System Design, 2014

On the Ambiguity, Finite-Valuedness, and Lossiness Problems in Acceptors and Transducers.
Proceedings of the Implementation and Application of Automata, 2014

Information Rate of Some Classes of Non-regular Languages: An Automata-Theoretic Approach - (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

On the Parikh Membership Problem for FAs, PDAs, and CMs.
Proceedings of the Language and Automata Theory and Applications, 2014

APDCM Introduction and Committees.
Proceedings of the 2014 IEEE International Parallel & Distributed Processing Symposium Workshops, 2014

On Decidability and Closure Properties of Language Classes with Respect to Bio-operations.
Proceedings of the DNA Computing and Molecular Programming - 20th International Conference, 2014

Automata with Reversal-Bounded Counters: A Survey.
Proceedings of the Descriptional Complexity of Formal Systems, 2014

Lossiness of Communication Channels Modeled by Transducers.
Proceedings of the Language, Life, Limits - 10th Conference on Computability in Europe, 2014

2013
On the open problem of Ginsburg concerning semilinear sets and related problems.
Theor. Comput. Sci., 2013

Similarity in languages and programs.
Theor. Comput. Sci., 2013

Preface.
Int. J. Found. Comput. Sci., 2013

How to synchronize the Heads of a Multitape Automaton.
Int. J. Found. Comput. Sci., 2013

Some Decision Problems Concerning NPDAs, Palindromes, and Dyck Languages.
Proceedings of the Implementation and Application of Automata, 2013

On the Boundedness Property of Semilinear Sets.
Proceedings of the Theory and Applications of Models of Computation, 2013

On Bounded Languages and Reversal-Bounded Automata.
Proceedings of the Language and Automata Theory and Applications, 2013

Execution Information Rate for Some Classes of Automata.
Proceedings of the Language and Automata Theory and Applications, 2013

APDCM Introduction.
Proceedings of the 2013 IEEE International Symposium on Parallel & Distributed Processing, 2013

Some Decision Questions Concerning the Time Complexity of Language Acceptors.
Proceedings of the Developments in Language Theory - 17th International Conference, 2013

2012
On the containment and equivalence problems for two-way transducers.
Theor. Comput. Sci., 2012

On synchronized multi-tape and multi-head automata.
Theor. Comput. Sci., 2012

One-reversal counter machines and multihead automata: Revisited.
Theor. Comput. Sci., 2012

Characterizations of Bounded semilinear Languages by One-Way and Two-Way Deterministic Machines.
Int. J. Found. Comput. Sci., 2012

Sheng Yu.
Int. J. Found. Comput. Sci., 2012

A Survey of Results on Stateless Multicounter Automata.
Fundam. Inform., 2012

How to Synchronize the Heads of a Multitape Automaton.
Proceedings of the Implementation and Application of Automata, 2012

Multitape NFA: Weak Synchronization of the Input Heads.
Proceedings of the SOFSEM 2012: Theory and Practice of Computer Science, 2012

Weak Synchronization and Synchronizability of Multitape Pushdown Automata and Turing Machines.
Proceedings of the Language and Automata Theory and Applications, 2012

APDCM Introduction.
Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium Workshops & PhD Forum, 2012

2011
Relational String Verification Using Multi-Track Automata.
Int. J. Found. Comput. Sci., 2011

On Strong Reversibility in P Systems and Related Problems.
Int. J. Found. Comput. Sci., 2011

On the Containment and Equivalence Problems for GSMs, Transducers, and Linear CFGs.
Proceedings of the Implementation and Application of Automata, 2011

One-Reversal Counter Machines and Multihead Automata: Revisited.
Proceedings of the SOFSEM 2011: Theory and Practice of Computer Science, 2011

APDCM Introduction.
Proceedings of the 25th IEEE International Symposium on Parallel and Distributed Processing, 2011

On Two-Way Transducers.
Proceedings of the Developments in Language Theory - 15th International Conference, 2011

On Synchronized Multitape and Multihead Automata.
Proceedings of the Descriptional Complexity of Formal Systems, 2011

Characterizations of Bounded Semilinear Languages by One-Way and Two-way Deterministic Machines.
Proceedings of the Automata and Formal Languages, 13th International Conference, 2011

2010
On decision problems for parameterized machines.
Theor. Comput. Sci., 2010

On stateless multihead automata: Hierarchies and the emptiness problem.
Theor. Comput. Sci., 2010

On sets of numbers accepted by P/T systems composed by join.
Theor. Comput. Sci., 2010

Bond computing systems: a biologically inspired and high-level dynamics model for pervasive computing.
Natural Computing, 2010

On spiking neural P systems.
Natural Computing, 2010

Preface.
Int. J. Found. Comput. Sci., 2010

On the universe, disjointness, and containment problems for simple machines.
Inf. Comput., 2010

Relational String Verification Using Multi-track Automata.
Proceedings of the Implementation and Application of Automata, 2010

Advances in parallel and distributed computing models - APDCM.
Proceedings of the 24th IEEE International Symposium on Parallel and Distributed Processing, 2010

On Decision Problems for Simple and Parameterized Machines.
Proceedings of the Developments in Language Theory, 14th International Conference, 2010

Computing with Cells: Membrane Systems.
Proceedings of the Computing and Combinatorics, 16th Annual International Conference, 2010

2009
Sequential SNP systems based on min/max spike number.
Theor. Comput. Sci., 2009

Asynchronous spiking neural P systems.
Theor. Comput. Sci., 2009

Preface.
Int. J. Found. Comput. Sci., 2009

On Languages Accepted by P/T Systems Composed of joins
Proceedings of the Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems, 2009

Symbolic String Verification: Combining String Analysis and Size Analysis.
Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2009

A Look Back at Some Early Results in Membrane Computing.
Proceedings of the Membrane Computing, 10th International Workshop, 2009

On Stateless Multihead Finite Automata and Multihead Pushdown Automata.
Proceedings of the Developments in Language Theory, 13th International Conference, 2009

Hierarchies and Characterizations of Stateless Multicounter Machines.
Proceedings of the Computing and Combinatorics, 15th Annual International Conference, 2009

On Stateless Multicounter Machines.
Proceedings of the Mathematical Theory and Computational Practice, 2009

2008
Minimum-cost delegation in service composition.
Theor. Comput. Sci., 2008

Computing with cells: membrane systems - some complexity issues.
IJPEDS, 2008

On spiking neural P systems and partially blind counter machines.
Natural Computing, 2008

Characterizations of some classes of spiking neural P systems.
Natural Computing, 2008

On Stateless Automata and P Systems.
Int. J. Found. Comput. Sci., 2008

Discrete Nondeterministic Modeling of the Fas Pathway.
Int. J. Found. Comput. Sci., 2008

On Counter Machines, Reachability Problems, and Diophantine Equations.
Int. J. Found. Comput. Sci., 2008

Symbolic String Verification: An Automata-Based Approach.
Proceedings of the Model Checking Software, 2008

On Stateless Multihead Automata: Hierarchies and the Emptiness Problem.
Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Computing with Cells: Membrane Systems.
Proceedings of the 9th International Symposium on Parallel Architectures, 2008

Sequentiality Induced by Spike Number in SNP Systems.
Proceedings of the DNA Computing, 14th International Meeting on DNA Computing, 2008

2007
Membrane Systems.
Proceedings of the Handbook of Parallel Computing - Models, Algorithms and Applications., 2007

Normal forms for spiking neural P systems.
Theor. Comput. Sci., 2007

Developments in language theory.
Theor. Comput. Sci., 2007

Preface.
Int. J. Found. Comput. Sci., 2007

Characterizing Regular Languages by Spiking Neural P Systems.
Int. J. Found. Comput. Sci., 2007

Bond Computing Systems: A Biologically Inspired and High-Level Dynamics Model for Pervasive Computing.
Proceedings of the Unconventional Computation, 6th International Conference, 2007

Spiking Neural P Systems: Some Characterizations.
Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

Asynchronous Spiking Neural P Systems: Decidability and Undecidability.
Proceedings of the DNA Computing, 13th International Meeting on DNA Computing, 2007

A q-Analogue of the Parikh Matrix Mapping.
Proceedings of the Formal Models, 2007

2006
Deterministic catalytic systems are not universal.
Theor. Comput. Sci., 2006

On partially blind multihead finite automata.
Theor. Comput. Sci., 2006

Characterizations of context-sensitive languages and other language classes in terms of symport/antiport P systems.
Theor. Comput. Sci., 2006

On the solvability of a class of diophantine equations and applications.
Theor. Comput. Sci., 2006

On the Computational Complexity of P Automata.
Natural Computing, 2006

Quality-Aware Service Delegation in Automated Web Service Composition: An Automata-Theoretic Approach.
Journal of Automata, Languages and Combinatorics, 2006

On the Decidability of Model-Checking for P Systems.
Journal of Automata, Languages and Combinatorics, 2006

On symport/antiport P systems with a small number of objects.
Int. J. Comput. Math., 2006

On the Computational Power of 1-Deterministic and Sequential P Systems.
Fundam. Inform., 2006

On Spiking Neural P Systems and Partially Blind Counter Machines.
Proceedings of the Unconventional Computation, 5th International Conference, 2006

Characterizations of Some Restricted Spiking Neural P Systems.
Proceedings of the Membrane Computing, 7th International Workshop, 2006

2005
On determinism versus nondeterminism in P systems.
Theor. Comput. Sci., 2005

On membrane hierarchy in P systems.
Theor. Comput. Sci., 2005

On composition and lookahead delegation of e-services modeled by automata, .
Theor. Comput. Sci., 2005

On two-way nondeterministic finite automata with one reversal-bounded counter.
Theor. Comput. Sci., 2005

On various notions of parallelism in P Systems.
Int. J. Found. Comput. Sci., 2005

On one-membrane P systems operating in sequential mode.
Int. J. Found. Comput. Sci., 2005

On Deterministic Catalytic Systems.
Proceedings of the Implementation and Application of Automata, 2005

On Model-Checking of P Systems.
Proceedings of the Unconventional Computation, 4th International Conference, 2005

On Symport/Antiport P Systems with One or Two Symbols.
Proceedings of the Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2005), 2005

Some Computational Issues in Membrane Computing.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

On Symport/Antiport P Systems and Semilinear Sets.
Proceedings of the Membrane Computing, 6th International Workshop, 2005

Some Recent Results Concerning Deterministic P Systems.
Proceedings of the Membrane Computing, 6th International Workshop, 2005

SPiDeR: P2P-Based Web Service Discovery.
Proceedings of the Service-Oriented Computing, 2005

Signaling P Systems and Verification Problems.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

On Bounded Symport/Antiport P Systems.
Proceedings of the DNA Computing, 11th International Workshop on DNA Computing, 2005

Counting Time in Computing with Cells.
Proceedings of the DNA Computing, 11th International Workshop on DNA Computing, 2005

On Sequential and 1-Deterministic P Systems.
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

Online and Minimum-Cost Ad Hoc Delegation in e-Service Composition.
Proceedings of the 2005 IEEE International Conference on Services Computing (SCC 2005), 2005

2004
Catalytic P systems, semilinear sets, and vector addition systems.
Theor. Comput. Sci., 2004

On two-way FA with monotonic counters and quadratic Diophantine equations.
Theor. Comput. Sci., 2004

Editorial.
Theor. Comput. Sci., 2004

On the computational complexity of membrane systems.
Theor. Comput. Sci., 2004

Past pushdown timed automata and safety verification.
Theor. Comput. Sci., 2004

Computing And Combinatorics Conference -- Cocoon'02.
Int. J. Found. Comput. Sci., 2004

Instance-Specific Solutions For Accelerating The Cky Parsing Of Large Context-Free Grammars.
Int. J. Found. Comput. Sci., 2004

Automata-Theoretic Techniques for Analyzing Infinite-State Systems.
Proceedings of the Implementation and Application of Automata, 2004

P Systems: Some Recent Results and Research Problems.
Proceedings of the Unconventional Programming Paradigms, 2004

Composability of Infinite-State Activity Automata.
Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

A Matrix q-Analogue of the Parikh Map.
Proceedings of the Exploring New Frontiers of Theoretical Informatics, 2004

Automated composition of e-services: lookaheads.
Proceedings of the Service-Oriented Computing, 2004

Modeling Affective Responses in Intelligent Tutoring Systems.
Proceedings of the IEEE International Conference on Advanced Learning Technologies, 2004

Real-Counter Automata and Their Decision Problems.
Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

On the Computational Complexity of P Automata.
Proceedings of the DNA Computing, 10th International Workshop on DNA Computing, 2004

The Power of Maximal Parallelism in P Systems.
Proceedings of the Developments in Language Theory, 2004

On P Systems Operating in Sequential Mode.
Proceedings of the 6th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2004, London, Ontario, Canada, July 26, 2004

2003
Verification in loosely synchronous queue-connected discrete timed automata.
Theor. Comput. Sci., 2003

Eliminating the storage tape in reachability constructions.
Theor. Comput. Sci., 2003

Generalized discrete timed automata: decidable approximations for safety verificatio.
Theor. Comput. Sci., 2003

Closure and decidability properties of some language classes with respect to ciliate bio-operations.
Theor. Comput. Sci., 2003

The ld and dlad Bio-Operations on Formal Languages.
Journal of Automata, Languages and Combinatorics, 2003

Characterizations of Catalytic Membrane Computing Systems.
Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

The Number of Membranes Matters.
Proceedings of the Membrane Computing, International Workshop, 2003

A Solvable Class of Quadratic Diophantine Equations with Applications to Verification of Infinite-State Systems.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Dense Counter Machines and Verification Problems.
Proceedings of the Computer Aided Verification, 15th International Conference, 2003

2002
Counter Machines and Verification Problems.
Theor. Comput. Sci., 2002

Augmenting the discrete timed automaton with other data structures.
Theor. Comput. Sci., 2002

Some Decision Problems Concerning Semilinearity and Commutation.
J. Comput. Syst. Sci., 2002

Verification in Queue-Connected Multicounter Machines.
Int. J. Found. Comput. Sci., 2002

The Existence of w-Chains for Transitive Mixed Linear Relations and Its Applications.
Int. J. Found. Comput. Sci., 2002

On Moving Object Queries.
Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2002

On the Emptiness Problem for Two-Way NFA with One Reversal-Bounded Counter.
Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

Workshop Introduction.
Proceedings of the 16th International Parallel and Distributed Processing Symposium (IPDPS 2002), 2002

Safety Verification for Two-Way Finite Automata with Monotonic Counters.
Proceedings of the Developments in Language Theory, 6th International Conference, 2002

Trajectory queries and octagons in moving object databases.
Proceedings of the 2002 ACM CIKM International Conference on Information and Knowledge Management, 2002

2001
On Reachability and Safety in Infinite-State Systems.
Int. J. Found. Comput. Sci., 2001

Past Pushdown Timed Automata.
Proceedings of the Implementation and Application of Automata, 2001

On Multi-way Spatial Joins with Direction Predicates.
Proceedings of the Advances in Spatial and Temporal Databases, 7th International Symposium, 2001

Moving Objects: Logical Relationships and Queries.
Proceedings of the Advances in Spatial and Temporal Databases, 7th International Symposium, 2001

On Removing the Pushdown Stack in Reachability Constructions.
Proceedings of the Algorithms and Computation, 12th International Symposium, 2001

Decision Questions Concerning Semilinearity, Morphisms, and Commutation of Languages.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Liveness Verification of Reversal-Bounded Multicounter Machines with a Free Counter.
Proceedings of the FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, 2001

Decidable Approximations on Generalized and Parameterized Discrete Timed Automata.
Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

Counter machines and the safety and disjointness problems for database queries with linear constraints.
Proceedings of the Where Mathematics, 2001

2000
Image compression for fast wavelet-based subregion retrieval.
Theor. Comput. Sci., 2000

Adaptive Load Sharing for Clustered Digital Library Servers.
Int. J. on Digital Libraries, 2000

Generalizing the Discrete Timed Automaton.
Proceedings of the Implementation and Application of Automata, 2000

Reachability and Safety in Queue Systems.
Proceedings of the Implementation and Application of Automata, 2000

Extending Rectangle Join Algorithms for Rectilinear Polygons.
Proceedings of the Web-Age Information Management, First International Conference, 2000

Toward Spatial Joins for Polygons.
Proceedings of the 12th International Conference on Scientific and Statistical Database Management, 2000

Conter Machines: Decidable Properties and Applications to Verification Problems.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

Workshop on Advances in Parallel and Distributed Computational Models.
Proceedings of the Parallel and Distributed Processing, 2000

Reachability Analysis for Some Models of Infinite-State Transition Systems.
Proceedings of the CONCUR 2000, 2000

Binary Reachability Analysis of Discrete Pushdown Timed Automata.
Proceedings of the Computer Aided Verification, 12th International Conference, 2000

1999
A Technique for Proving Decidability of Containment and Equivalence of Linear Constraint Queries.
J. Comput. Syst. Sci., 1999

An Index Structure for Spatial Joins in Linear Constraint Databases.
Proceedings of the 15th International Conference on Data Engineering, 1999

Counter Machines: Decision Problems and Applications.
Proceedings of the Jewels are Forever, 1999

1998
Adaptive Partitioning and Scheduling for Enhancing WWW Application Performance.
J. Parallel Distrib. Comput., 1998

Adaptive Load Sharing for Clustered Digital Library Servers.
Proceedings of the Seventh IEEE International Symposium on High Performance Distributed Computing, 1998

1997
On the Parallel Complexity of Loops.
Theor. Comput. Sci., 1997

Parallel Progressive Radiosity with Adaptive Meshing.
J. Parallel Distrib. Comput., 1997

Toward a Scalable Distributed {WWW} Server on Workstation Clusters.
J. Parallel Distrib. Comput., 1997

On the Complexity of Commutativity Analysis.
Int. J. Found. Comput. Sci., 1997

On the Containment and Equivalence of Database Queries with Linear Constraints.
Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1997

A Compact Storage Scheme for Fast Wavelet-Based Subregion Retrieval.
Proceedings of the Computing and Combinatorics, Third Annual International Conference, 1997

1996
Performance Prediction in Symbolic Scheduling of Partitioned Programs with Weight Variation.
J. Parallel Distrib. Comput., 1996

Parallel Progressive Radiosity with Adaptive Meshing.
Proceedings of the Parallel Algorithms for Irregularly Structured Problems, 1996

SWEB: Towards a Scalable World Wide Web Server on Multicomputers.
Proceedings of IPPS '96, 1996

Experimental Studies on a Compact Storage Scheme for Wavelet-Based Multiresolution Subregion Retrieval.
Proceedings of the 6th Data Compression Conference (DCC '96), Snowbird, Utah, March 31, 1996

On the Complexity of Commutativity Analysis.
Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

Scalability Issues for High Performance Digital Libraries on the World Wide Web.
Proceedings of the Third Forum on Research and Technology Advances in Digital Library, 1996

1995
New Decidability Results Concerning Two-Way Counter Machines.
SIAM J. Comput., 1995

A note on parsing pattern languages.
Pattern Recognition Letters, 1995

An Optimal Shortest Path Parallel Algorithm for Permutation Graphs.
J. Parallel Distrib. Comput., 1995

On symbolic scheduling and parallel complexity of loops.
Proceedings of the Seventh IEEE Symposium on Parallel and Distributed Processing, 1995

1994
Some Results Concerning 2-D On-Line Tessellation Acceptors and 2-D Alternating Finite Automata.
Theor. Comput. Sci., 1994

Fast Parallel Algorithms for Solving Triangular Systems of Linear Equations on the Hypercube.
J. Parallel Distrib. Comput., 1994

Some Efficient Algorithms for Permutation Graphs.
J. Algorithms, 1994

On Communication-Bounded Synchronized Alternating Finite Automata.
Acta Inf., 1994

On the Parallel Complexity of Solving Recurrence Equations.
Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

Transformations Between Boundary Codes, Run Length Codes, and Linear Quadtrees.
Proceedings of the 8th International Symposium on Parallel Processing, 1994

A flow based approach to the pin redistribution problem for multi-chip modules.
Proceedings of the Fourth Great Lakes Symposium on Design Automation of High Performance VLSI Systems, 1994

On Some Open Problems Concerning the Complexity of Cellular Arrays.
Proceedings of the Results and Trends in Theoretical Computer Science, 1994

1993
Synchronized Finite Automata and 2DFA Reductions.
Theor. Comput. Sci., 1993

A Note on Simple Programs with Two Variables.
Theor. Comput. Sci., 1993

Quadtree Building Algorithms on an SIMD Hypercube.
J. Parallel Distrib. Comput., 1993

On Efficient Parallel Algorithms for Solving Set Recurrence Equations.
J. Algorithms, 1993

On the Equivalence of Two-Way Pushdown Automata and Counter Machines Over Bounded Languages.
Int. J. Found. Comput. Sci., 1993

On the Equivalence of Two-way Pushdown Automata and Counter Machines over Bounded Languages.
Proceedings of the STACS 93, 1993

On the Communication Complexity of Parallel Computation.
Proceedings of the Mathematical Foundations of Computer Science 1993, 1993

On the Shortest Path Problems for Permutation Graphs.
Proceedings of the Seventh International Parallel Processing Symposium, 1993

Finding Articulation Points and Bridges of Permutation Graphs.
Proceedings of the 1993 International Conference on Parallel Processing, 1993

New Decidability Results Concerning Two-way Counter Machines and Applications.
Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

1992
On Space-Bounded Synchronized Alternating Turing Machines.
Theor. Comput. Sci., 1992

A Characterization of Exponential-Time Languages by Alternating Context-Free Grammars.
Theor. Comput. Sci., 1992

String Editing on a One-Way Linear Array of Finite-State Machines.
IEEE Trans. Computers, 1992

Iterative algorithms for the planar convex hull problem on mesh-connected arrays.
Parallel Computing, 1992

A hierarchy result for 2-dimensional TM's operating in small space.
Inf. Sci., 1992

Quadtree Building Algorithms on an SIMD Hypercube.
Proceedings of the 6th International Parallel Processing Symposium, 1992

New Results Concerning Synchronized Finite Automata.
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

1991
Some Classes of Languages in NC¹
Inf. Comput., January, 1991

Parallel Parsing on a One-Way Linear Array of Finite-State Machines.
Theor. Comput. Sci., 1991

Parallel Regognition and Parsing on the Hypercube.
IEEE Trans. Computers, 1991

The Power of Alternating One-Reversal Counters and Stacks.
SIAM J. Comput., 1991

Learning Regular Languages from Counterexamples.
J. Comput. Syst. Sci., 1991

On Resetiting DLBA's.
Bulletin of the EATCS, 1991

Some Results Concerning 2-D On-line Tessellation Acceptors and 2-D Alternating Finite Automata.
Proceedings of the Mathematical Foundations of Computer Science 1991, 1991

Fast Parallel Algorithms for Solving Triangular Systems of Linear Equations on the Hypercube.
Proceedings of the Fifth International Parallel Processing Symposium, Proceedings, Anaheim, California, USA, April 30, 1991

Triangulation in a Plane and 3-D Convex Hull on Mesh-Connected Arrays and Hypercubes.
Proceedings of the Fifth International Parallel Processing Symposium, Proceedings, Anaheim, California, USA, April 30, 1991

Triangulation Voronoi Diagram and Convex Hull in k-Space on Mesh-Connected Arrays and Hypercubes.
Proceedings of the International Conference on Parallel Processing, 1991

On Space-bounded Synchronized Alternating Turing Machines.
Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

1990
Systolic algorithms for some scheduling and graph problems.
VLSI Signal Processing, 1990

String processing on the hypercube.
IEEE Trans. Acoustics, Speech, and Signal Processing, 1990

On Mapping Systolic Algorithms onto the Hypercube.
IEEE Trans. Parallel Distrib. Syst., 1990

An efficient all-parses systolic algorithm for general context-free parsing.
International Journal of Parallel Programming, 1990

Efficient parallel algorithms for solving set recurrence equations and applications.
Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing, 1990

String Editing on a One-Way Linear Array of Finite-State Machines.
Proceedings of the 1990 International Conference on Parallel Processing, 1990

Iterative Algorithms for Planar Convex Hull on Mesh-Connected Arrays.
Proceedings of the 1990 International Conference on Parallel Processing, 1990

1989
Efficient Simulations of Simple Models of Parallel Computation by Time-Bounded ATMs and Space-Bounded TMs.
Theor. Comput. Sci., 1989

Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation.
SIAM J. Comput., 1989

On Iterative and Cellular Tree Arrays.
J. Comput. Syst. Sci., 1989

Optimal Simulation of Tree Arrays by Linear Arrays.
Inf. Process. Lett., 1989

An Efficient All-Parses Systolic Algorithm for General Context-Free Parsing.
Proceedings of the Algorithms and Data Structures, 1989

On Mapping Systolic Algorithms onto the Hypercube.
Proceedings of the International Conference on Parallel Processing, 1989

Parallel Parsing on a One-way Linear Array of Finite-State Machines.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1989

1988
Two-Dimensional Iterative Arrays: Characterizations and Applications.
Theor. Comput. Sci., 1988

Relating the Power of Cellular Arrays to Their Closure Properties.
Theor. Comput. Sci., 1988

On Two-Dimensional Via Assignment for Single-Row Routing.
IEEE Trans. Computers, 1988

Systolic Tree Implementation of Data Structures.
IEEE Trans. Computers, 1988

Two-Dimensional Convolution on a Pyramid Computer.
IEEE Trans. Pattern Anal. Mach. Intell., 1988

Sublogarithmic-Space Turing Machines, Nonuniform Space Complexity, and Closure Properties.
Mathematical Systems Theory, 1988

On the power of one-way communication.
J. ACM, 1988

Some Subclasses of Context-Free Languages In NC1.
Inf. Process. Lett., 1988

Efficient Simulations of Simple Models of Parallel Computation by Time-Bounded ATM's and Space-Bounded TM's.
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

Learning Regular Languages From Counterexamples.
Proceedings of the First Annual Workshop on Computational Learning Theory, 1988

Trading reversals for alternation.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

On Some Languages in NC.
Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987
VLSI algorithms for solving recurrence equations and applications.
IEEE Trans. Acoustics, Speech, and Signal Processing, 1987

Single-Row Routing with Crossover Bound.
IEEE Trans. on CAD of Integrated Circuits and Systems, 1987

Parallel Parsing on a One-Way Array of Finite-State Machines.
IEEE Trans. Computers, 1987

On Efficient Simulations of Systolic Arrays of Random-Access Machines.
SIAM J. Comput., 1987

On One-Way Cellular Arrays.
SIAM J. Comput., 1987

Some Observations Concerning Alternating Turing Machines Using Small Space.
Inf. Process. Lett., 1987

Two-Dimensional Convolution on a Pyramid Computer.
Proceedings of the International Conference on Parallel Processing, 1987

On the Computing Power of One-Way Cellular Arrays.
Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

Relating the Degree of Ambiguity of Finite Automata to the Succinctness of their Representation.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1987

1986
On Pebble Automata.
Theor. Comput. Sci., 1986

Designing Systolic Algorithms Using Sequential Machines.
IEEE Trans. Computers, 1986

On Sparseness, Ambiguity and other Decision Problems for Acceptors and Transducers.
Proceedings of the STACS 86, 1986

Systolic Arrays: Characterizations and Complexity.
Proceedings of the Mathematical Foundations of Computer Science 1986, 1986

Parallel Parsing on a One-Way Array of Finite-State Machines.
Proceedings of the International Conference on Parallel Processing, 1986

Systolic Tree Implementation of Data Structures.
Proceedings of the International Conference on Parallel Processing, 1986

On the Power of One-Way Communication
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985
On Simple Programs with Primitive Conditional Statements
Information and Control, April, 1985

The Equivalence Problem and Correctness Formulas for a Simple Class of Programs
Information and Control, April, 1985

Fast Parallel Language Recognition by Cellular Automata.
Theor. Comput. Sci., 1985

On Efficient Recognition of Transductions and Relations.
Theor. Comput. Sci., 1985

Sequential Machine Characterizations of Trellis and Cellular Automata and Applications.
SIAM J. Comput., 1985

Some results concerning linear iterative (systolic) arrays.
J. Parallel Distrib. Comput., 1985

On Space and Time Efficient TM Simulations of Some Restricted Classes of PDA's
Information and Control, 1985

Some Characterizations of Multihead Finite Automata
Information and Control, 1985

1984
Characterizations and Computational Complexity of Systolic Trellis Automata.
Theor. Comput. Sci., 1984

A Note on the Complexity of Program Evaluation.
Mathematical Systems Theory, 1984

A Characterization of Systolic Binary Tree Automata and Applications.
Acta Inf., 1984

The Equivalence Problem and Correctness Formulas for a Simple Class of Programs (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

Space and Time Efficient Simulations and Characterizations of Some Restricted Classes of PDAs.
Proceedings of the Automata, 1984

Designing Systolic Algorithms Using Sequential Machines
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
On the Simplification and Equivalence Problems for Straight-Line Programs
J. ACM, July, 1983

Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
J. ACM, January, 1983

Simple Programming Languages and Restricted Classes of Turing Machines.
Theor. Comput. Sci., 1983

On the Control Power of Integer Division.
Theor. Comput. Sci., 1983

On Some Decision Questions Concerning Pushdown Machines.
Theor. Comput. Sci., 1983

On the Finite-Valuedness Problem for Sequential Machines.
Theor. Comput. Sci., 1983

Some Time-Space Tradeoff Results Concerning Single-Tape and Offline TM's.
SIAM J. Comput., 1983

On the Space and Time Complexity of Functions Computable by Simple Programs.
SIAM J. Comput., 1983

A Note on Finitely-Valued and Finitely Ambiguous Transducers.
Mathematical Systems Theory, 1983

On the Zero-Inequivalence Problem for Loop Programs.
J. Comput. Syst. Sci., 1983

1982
On the Complexity of Simple Arithmetic Expressions.
Theor. Comput. Sci., 1982

2DST Mapppings on Languages and Related Problems.
Theor. Comput. Sci., 1982

Some Simplified Undecidable and NP-Hard Problems for Simple Programs.
Theor. Comput. Sci., 1982

The Complexity of the Equivalence Problem for Simple Loop-Free Programs.
SIAM J. Comput., 1982

Straight-Line Programs with One Input Variable.
SIAM J. Comput., 1982

(Semi)Alternating Stack Automata.
Mathematical Systems Theory, 1982

On Some Decision Problems for RAM Programs.
J. Comput. Syst. Sci., 1982

A Generalization of the Fast LUP Matrix Decomposition Algorithm and Applications.
J. Algorithms, 1982

Two-Way Counter Machines and Diophantine Equations.
J. ACM, 1982

1981
The Complexity of the Equivalence Problem for two Characterizations of Presburger Sets.
Theor. Comput. Sci., 1981

Characterizations of Presburger Functions.
SIAM J. Comput., 1981

On Restricted One-counter Machines.
Mathematical Systems Theory, 1981

The Complexity of Decision Problems for Finite-Turn Multicounter Machines.
J. Comput. Syst. Sci., 1981

The Complexity of the Equivalence Problem for Simple Programs.
J. ACM, 1981

On the Decidability of Equivalence for Deterministic Pushdown Transducers.
Inf. Process. Lett., 1981

Probabilistic Algorithms and Straight-Line Programs for Some Rank Decision Problems.
Inf. Process. Lett., 1981

Deterministic and Probabilistic Algorithms for Maximum Bipartite Matching Via Fast Matrix Multiplication.
Inf. Process. Lett., 1981

On the Complexity of Simple Arithmetic Expressions.
Proceedings of the Automata, 1981

The Complexity of Decision Problems for Finite-Turn Multicounter Machines.
Proceedings of the Automata, 1981

Two-Way Counter Machines and Diophantine Equations
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980
Path Systems: Constructions, Solutions and Applications.
SIAM J. Comput., 1980

A Note on the Parallel Complexity of Computing the Rank of Order n Matrices.
Inf. Process. Lett., 1980

The Complexity of the Equivalence Problem for Straight-Line Programs
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

1979
Restricted One-Counter Machines with Undecidable Universe Problems.
Mathematical Systems Theory, 1979

Simple Counter Machines and Number-Theoretic Problems.
J. Comput. Syst. Sci., 1979

Some Decision Problems Concerning Sequential Transducers and Checking Automata.
J. Comput. Syst. Sci., 1979

An NP-Complete Number-Theoretic Problem.
J. ACM, 1979

On the Space Complexity of Recursive Algorithms.
Inf. Process. Lett., 1979

The Complexity of the Equivalence Problem for Counter Machines, Semilinear Sets, and Simple Programs
Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

1978
On Two-Way Sequential Transductions of Full Semi-AFL's.
Theor. Comput. Sci., 1978

The Unsolvability of the Equivalence Problem for epsilon-Free NGSM's with Unary Input (Output) Alphabet and Applications.
SIAM J. Comput., 1978

Approximation Algorithms for Certain Scheduling Problems.
Math. Oper. Res., 1978

Reversal-Bounded Multicounter Machines and Their Decision Problems.
J. ACM, 1978

An NP-Complete Number-Theoretic Problem
Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978

1977
Bounds for LPT Schedules on Uniform Processors.
SIAM J. Comput., 1977

Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors.
J. ACM, 1977

The Unsolvability of the Equivalence Problem for epsilon-free NGSM's with Unary Input (Output) Alphabet and Applications
Proceedings of the 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October, 1977

1976
Finite Automata with Multiplication.
Theor. Comput. Sci., 1976

A Useful Device for Showing the Solvability of Some Decision Problems.
J. Comput. Syst. Sci., 1976

A Useful Device for Showing the Solvability of Some Decision Problems
Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976

1975
Polynomially Complete Fault Detection Problems.
IEEE Trans. Computers, 1975

Hierarchies of Turing Machines with Restricted Tape Alphabet Size.
J. Comput. Syst. Sci., 1975

Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems.
J. ACM, 1975

1974
A Hierarchy Theorem for Polynomial-Space Recognition.
SIAM J. Comput., 1974

A Note on Semilinear Sets and Bounded-Reversal Multihead Pushdown Automata.
Inf. Process. Lett., 1974

On 3-Head Versus 2-Head Finite Automata.
Acta Inf., 1974

1973
On Two-way Multihead Automata.
J. Comput. Syst. Sci., 1973

Controlled pushdown automata.
Inf. Sci., 1973

1972
A Note Concerning Nondeterministic Tape Complexities.
J. ACM, 1972

1971
Characterizations of Transductions Defined by Abstract Families of Transducers.
Mathematical Systems Theory, 1971

Characterizations of Some Tape and Time Complexity Classes of Turing Machines in Terms of Multihead and Auxiliary Stack Automata.
J. Comput. Syst. Sci., 1971

1970
Simple Matrix Languages
Information and Control, November, 1970

Tape-Bounded Turing Acceptors and Principal AFLs.
J. Comput. Syst. Sci., 1970

1968
Multi-Tape and Multi-Head Pushdown Automata
Information and Control, November, 1968

1967
On the Equivalence of Finite-State Sequential Machine Models.
IEEE Trans. Electronic Computers, 1967

Two-Way Pushdown Automata
Information and Control, 1967


  Loading...