Oscar H. Ibarra

According to our database1, Oscar H. Ibarra authored at least 340 papers between 1967 and 2020.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

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

IEEE Fellow

IEEE Fellow 1992, "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

2020
Space Complexity of Stack Automata Models.
Proceedings of the Developments in Language Theory - 24th International Conference, 2020

2019
On counting functions and slenderness of languages.
Theor. Comput. Sci., 2019

On families of full trios containing counter machine languages.
Theor. Comput. Sci., 2019

State grammars with stores.
Theor. Comput. Sci., 2019

Insertion operations on deterministic reversal-bounded counter machines.
J. Comput. Syst. Sci., 2019

On store languages and applications.
Inf. Comput., 2019

2018
On store languages of language acceptors.
Theor. Comput. Sci., 2018

Variations of checking stack automata: Obtaining unexpected decidability properties.
Theor. Comput. Sci., 2018

Grammatical characterizations of NPDAs and VPDAs with counters.
Theor. Comput. Sci., 2018

On the Density of Languages Accepted by Turing Machines and Other Machine Models.
J. Autom. Lang. Comb., 2018

On the Density of Context-Free and Counter Languages.
Int. J. Found. Comput. Sci., 2018

Accepting runs in a two-way finite automaton.
Inf. Comput., 2018

On the complexity and decidability of some problems involving shuffle.
Inf. Comput., 2018

Semilinearity of Families of Languages.
Proceedings of the Implementation and Application of Automata, 2018

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

On Counting Functions of Languages.
Proceedings of the Developments in Language Theory - 22nd International Conference, 2018

Generalizations of Checking Stack Automata: Characterizations and Hierarchies.
Proceedings of the Developments in Language Theory - 22nd International Conference, 2018

Input-Position-Restricted Models of Language Acceptors.
Proceedings of the Reversibility and Universality, 2018

2017
On the overlap assembly of strings and languages.
Nat. Comput., 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

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

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.
Nat. Comput., 2016

On decidability and closure properties of language classes with respect to bio-operations.
Nat. Comput., 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

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

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

2014
Weak Synchronization and Synchronizability of Multi-tape Pushdown Automata and Turing Machines.
J. Autom. Lang. Comb., 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 Syst. Des., 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

Automata with Reversal-Bounded Counters: A Survey.
Proceedings of the Descriptional Complexity of Formal Systems, 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

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

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

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

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

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.
Nat. Comput., 2010

On spiking neural P systems.
Nat. Comput., 2010

On the universe, disjointness, and containment problems for simple machines.
Inf. Comput., 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

On Nonuniversal Symport/Antiport P Systems.
Proceedings of the Algorithmic Bioprocesses, 2009

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

Computing with cells: membrane systems - some complexity issues.
Int. J. Parallel Emergent Distributed Syst., 2008

On spiking neural P systems and partially blind counter machines.
Nat. Comput., 2008

Characterizations of some classes of spiking neural P systems.
Nat. Comput., 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

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

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.
Nat. Comput., 2006

Quality-Aware Service Delegation in Automated Web Service Composition: An Automata-Theoretic Approach.
J. Autom. Lang. Comb., 2006

On the Decidability of Model-Checking for P Systems.
J. Autom. Lang. Comb., 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

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

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.
J. Autom. Lang. Comb., 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 Distributed Comput., 1998

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

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

Toward a Scalable Distributed {WWW} Server on Workstation Clusters.
J. Parallel Distributed 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 Distributed Comput., 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, USA, March 31, 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 Recognit. Lett., 1995

An Optimal Shortest Path Parallel Algorithm for Permutation Graphs.
J. Parallel Distributed 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 Distributed Comput., 1994

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

On Communication-Bounded Synchronized Alternating Finite Automata.
Acta Informatica, 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 Distributed 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 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 Comput., 1992

A hierarchy result for 2-dimensional TM's operating in small space.
Inf. Sci., 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

On resetting DLBA's.
SIGACT News, 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.
Bull. EATCS, 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

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

String processing on the hypercube.
IEEE Trans. Acoust. Speech Signal Process., 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.
Int. J. Parallel Program., 1990

Efficient parallel algorithms for solving set recurrence equations and applications.
Proceedings of the Second IEEE Symposium on Parallel and Distributed 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

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.
Math. Syst. 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

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. Acoust. Speech Signal Process., 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

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

1985
On Simple Programs with Primitive Conditional Statements
Inf. Control., April, 1985

The Equivalence Problem and Correctness Formulas for a Simple Class of Programs
Inf. 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 Distributed Comput., 1985

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

Some Characterizations of Multihead Finite Automata
Inf. Control., 1985

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

A Note on the Complexity of Program Evaluation.
Math. Syst. Theory, 1984

A Characterization of Systolic Binary Tree Automata and Applications.
Acta Informatica, 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

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.
Math. Syst. 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.
Math. Syst. 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.
Math. Syst. 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

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.
Math. Syst. 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

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

Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors.
J. ACM, 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

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 Informatica, 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.
Math. Syst. 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
Inf. Control., November, 1970

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

1968
Multi-Tape and Multi-Head Pushdown Automata
Inf. Control., November, 1968

1967
On the Equivalence of Finite-State Sequential Machine Models.
IEEE Trans. Electron. Comput., 1967

Two-Way Pushdown Automata
Inf. Control., 1967


  Loading...