Martin Kutrib

From MaRDI portal


List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

PublicationDate of PublicationType
On properties of languages accepted by deterministic pushdown automata with translucent input letters
 
2025-01-20Paper
Reversible Computations of One-Way Counter Automata
RAIRO - Theoretical Informatics and Applications
2024-04-16Paper
Reversible Two-Party Computations
Electronic Proceedings in Theoretical Computer Science
2024-04-09Paper
On the power of pushing or stationary moves for input-driven pushdown automata
Theoretical Computer Science
2024-04-04Paper
Sweeping input-driven pushdown automata
Implementation and Application of Automata
2024-02-28Paper
Iterative arrays with finite inter-cell communication
Natural Computing
2024-02-16Paper
Iterative arrays with self-verifying communication cell
Natural Computing
2024-02-16Paper
Shrinking one-way cellular automata
Natural Computing
2024-02-09Paper
Reversible computations of one-way counter automata
 
2024-02-06Paper
25 editions of DCFS: origins and directions
 
2024-02-06Paper
Revisiting the cutting of the firing squad synchronization
Natural Computing
2023-11-30Paper
scientific article; zbMATH DE number 7770052 (Why is no real title available?)
 
2023-11-23Paper
Tree-walking-storage automata
Developments in Language Theory
2023-11-16Paper
One-dimensional pattern generation by cellular automata
Natural Computing
2023-09-01Paper
Complexity of exclusive nondeterministic finite automata
Descriptional Complexity of Formal Systems
2023-08-17Paper
Input-Driven Double-Head Pushdown Automata
International Journal of Foundations of Computer Science
2023-08-15Paper
Reversible Top-Down Syntax Analysis
International Journal of Foundations of Computer Science
2023-08-15Paper
Iterated uniform finite-state transducers on unary languages
Theoretical Computer Science
2023-08-01Paper
Self-verifying Cellular Automata
Developments in Language Theory
2023-06-30Paper
Syntax checking either way
Theoretical Computer Science
2023-06-21Paper
State complexity of finite partial languages
Theoretical Computer Science
2023-06-21Paper
State complexity of finite partial languages
 
2023-01-18Paper
Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power
 
2022-12-16Paper
Optimizing reversible programs
 
2022-11-11Paper
State complexity of partial word finite automata
 
2022-11-09Paper
scientific article; zbMATH DE number 7584596 (Why is no real title available?)
 
2022-09-14Paper
Syntax checking either way
 
2022-08-16Paper
On the power of pushing or stationary moves for input-driven pushdown automata
 
2022-08-16Paper
Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*
Fundamenta Informaticae
2022-07-14Paper
String assembling systems: comparison to sticker systems and decidability
 
2022-07-06Paper
Cellular Automata and Language Theory
Cellular Automata
2022-04-28Paper
Finite automata with undirected state graphs
Acta Informatica
2022-04-01Paper
Reversible top-down syntax analysis
 
2022-03-25Paper
One-dimensional pattern generation by cellular automata
 
2022-03-24Paper
Iterated uniform finite-state transducers on unary languages
 
2022-03-24Paper
Boolean kernels of context-free languages
 
2022-03-22Paper
Descriptional complexity of iterated uniform finite-state transducers
Information and Computation
2022-03-14Paper
Descriptional complexity of regular languages
 
2022-02-04Paper
Digging input-driven pushdown automata
RAIRO - Theoretical Informatics and Applications
2022-01-12Paper
Input-driven double-head pushdown automata
 
2021-12-13Paper
On the descriptional complexity of operations on semilinear sets
 
2021-12-13Paper
Reversible pushdown transducers
Information and Computation
2021-11-25Paper
Self-verifying pushdown and queue automata
Fundamenta Informaticae
2021-11-15Paper
Two-Sided Strictly Locally Testable Languages
Fundamenta Informaticae
2021-11-15Paper
Compiling Janus to RSSA
Reversible Computation
2021-11-03Paper
String generation by cellular automata
Complex Systems
2021-09-08Paper
Self-verifying cellular automata
 
2021-08-25Paper
Iterated uniform finite-state transducers: descriptional complexity of nondeterminism and two-way motion
 
2021-07-14Paper
Cellular string generators
 
2021-07-08Paper
Measuring communication in parallel communicating finite automata
 
2021-06-22Paper
Input-driven multi-counter automata
Theoretical Computer Science
2021-06-03Paper
Automata that may change their mind
 
2021-05-12Paper
On two-sided locally testable languages
 
2021-05-12Paper
Transductions computed by one-dimensional cellular automata
 
2021-04-27Paper
Boosting reversible pushdown and queue machines by preprocessing
International Journal of Foundations of Computer Science
2021-04-19Paper
The magic number problem for subregular language families
 
2021-02-24Paper
Bounded languages meet cellular automata with sparse communication
 
2021-01-26Paper
On the number of membranes in unary P systems
 
2021-01-26Paper
scientific article; zbMATH DE number 7301306 (Why is no real title available?)
 
2021-01-26Paper
Multi-head finite automata: characterizations, concepts and open problems
 
2021-01-20Paper
Multi-stranded string assembling systems
 
2020-10-22Paper
Kernels of sub-classes of context-free languages
SOFSEM 2020: Theory and Practice of Computer Science
2020-07-20Paper
Finite automata with undirected state graphs
Descriptional Complexity of Formal Systems
2020-06-30Paper
Cellular automata: descriptional complexity and decidability
Reversibility and Universality
2020-05-28Paper
Queue Automata: Foundations and Developments
Reversibility and Universality
2020-05-28Paper
Non-recursive trade-offs are ``almost everywhere
 
2020-05-12Paper
Descriptional complexity of iterated uniform finite-state transducers
Descriptional Complexity of Formal Systems
2020-05-12Paper
Input-driven multi-counter automata
Implementation and Application of Automata
2020-05-06Paper
Iterative arrays with set storage
 
2020-03-12Paper
One-time nondeterministic computations
International Journal of Foundations of Computer Science
2019-12-10Paper
Iterative arrays with finite inter-cell communication
 
2019-12-05Paper
Iterative arrays with self-verifying communication cell
 
2019-12-05Paper
Transducing reversibly with finite state machines
Theoretical Computer Science
2019-08-20Paper
Expressive capacity of subregular expressions
RAIRO - Theoretical Informatics and Applications
2019-07-18Paper
Diving into the queue
RAIRO - Theoretical Informatics and Applications
2019-07-18Paper
Recent trends in descriptional complexity of formal languages
 
2019-07-03Paper
Operational state complexity and decidability of jumping finite automata
International Journal of Foundations of Computer Science
2019-06-24Paper
Reversible pushdown transducers
Developments in Language Theory
2018-11-22Paper
Boosting pushdown and queue machines by preprocessing
 
2018-11-07Paper
Parametrizing string assembling systems
 
2018-11-07Paper
Structure and Complexity of Some Subregular Language Families
The Role of Theory in Computer Science
2018-09-20Paper
Cutting the Firing Squad Synchronization
Lecture Notes in Computer Science
2018-07-06Paper
Minimal reversible deterministic finite automata
International Journal of Foundations of Computer Science
2018-05-15Paper
Descriptional complexity of bounded regular languages
 
2018-03-29Paper
Descriptional complexity of limited automata
Information and Computation
2018-03-21Paper
Reversible nondeterministic finite automata
 
2018-03-16Paper
Fast one-way cellular automata with reversible Mealy cells
 
2018-03-08Paper
Deterministic stack transducers
International Journal of Foundations of Computer Science
2018-02-22Paper
The degree of irreversibility in deterministic finite automata
International Journal of Foundations of Computer Science
2018-02-22Paper
Reversible limited automata
Fundamenta Informaticae
2018-01-19Paper
Tinput-driven pushdown, counter, and stack automata
Fundamenta Informaticae
2018-01-19Paper
Reversible queue automata
Fundamenta Informaticae
2017-11-09Paper
Operational state complexity and decidability of jumping finite automata
 
2017-10-13Paper
One-time nondeterministic computations
 
2017-08-31Paper
Transducing reversibly with finite state machines
Implementation and Application of Automata
2017-08-22Paper
Concatenation-free languages
Theoretical Computer Science
2017-06-19Paper
The chop of languages
Theoretical Computer Science
2017-06-15Paper
One-way reversible multi-head finite automata
Theoretical Computer Science
2017-06-15Paper
When input-driven pushdown automata meet reversiblity
RAIRO - Theoretical Informatics and Applications
2017-03-24Paper
Self-assembling pushdown automata
 
2016-12-16Paper
scientific article; zbMATH DE number 6665209 (Why is no real title available?)
 
2016-12-16Paper
Descriptional complexity of bounded regular languages
Descriptional Complexity of Formal Systems
2016-11-09Paper
The degree of irreversibility in deterministic finite automata
Implementation and Application of Automata
2016-11-09Paper
Deterministic stack transducers
Implementation and Application of Automata
2016-11-09Paper
A hierarchy of fast reversible Turing machines
Reversible Computation
2016-09-30Paper
One-way cellular automata, bounded languages, and minimal communication
Journal of Automata, Languages and Combinatorics
2016-09-29Paper
Hairpin finite automata
Journal of Automata, Languages and Combinatorics
2016-09-29Paper
On measuring non-recursive trade-offs
Journal of Automata, Languages and Combinatorics
2016-09-29Paper
Boosting reversible pushdown machines by preprocessing
Reversible Computation
2016-08-10Paper
The chop of languages
 
2016-07-26Paper
Set automata
International Journal of Foundations of Computer Science
2016-06-23Paper
On one-way one-bit \(O\) (one)-message cellular automata
Electronic Notes in Theoretical Computer Science
2016-06-09Paper
Deterministic one-way Turing machines with sublinear space
Fundamenta Informaticae
2016-05-11Paper
Returning parallel communicating finite automata with communication bounds: hierarchies, decidabilities, and undecidabilities
International Journal of Foundations of Computer Science
2016-04-15Paper
Input-Driven Queue Automata with Internal Transductions
Language and Automata Theory and Applications
2016-04-13Paper
Reversible shrinking two-pushdown automata
Language and Automata Theory and Applications
2016-04-13Paper
One-way reversible multi-head finite automata
Reversible Computation
2015-11-30Paper
Minimal reversible deterministic finite automata
Developments in Language Theory
2015-11-10Paper
The size of one-way cellular automata
 
2015-11-02Paper
Expressive capacity of concatenation freeness
Implementation and Application of Automata
2015-09-23Paper
Reversible and irreversible computations of deterministic finite-state devices
Mathematical Foundations of Computer Science 2015
2015-09-16Paper
Reversible limited automata
Lecture Notes in Computer Science
2015-09-15Paper
Tinput-Driven Pushdown Automata
Lecture Notes in Computer Science
2015-09-15Paper
Aspects of reversibility for classical automata
Computing with New Resources
2015-09-08Paper
On simulation cost of unary limited automata
Descriptional Complexity of Formal Systems
2015-08-07Paper
Shrinking One-Way Cellular Automata
Cellular Automata and Discrete Complex Systems
2015-08-07Paper
Complexity of one-way cellular automata
Cellular Automata and Discrete Complex Systems
2015-08-04Paper
Real-time reversible one-way cellular automata
Cellular Automata and Discrete Complex Systems
2015-08-04Paper
Deterministic input-driven queue automata: finite turns, decidability, and closure properties
Theoretical Computer Science
2015-05-18Paper
Stateless one-way multi-head finite automata with pebbles
International Journal of Foundations of Computer Science
2015-04-23Paper
Complexity of operation problems
Language, Life, Limits
2015-02-25Paper
Simulations of unary one-way multi-head finite automata
International Journal of Foundations of Computer Science
2015-02-09Paper
Parameterized Prefix Distance between Regular Languages
SOFSEM 2014: Theory and Practice of Computer Science
2015-01-13Paper
Head and state hierarchies for unary multi-head finite automata
Acta Informatica
2014-12-03Paper
Deterministic set automata
Developments in Language Theory
2014-10-14Paper
Measuring communication in automata systems (invited paper)
Developments in Language Theory
2014-10-14Paper
Degrees of reversibility for DFA and DPDA
Reversible Computation
2014-09-02Paper
Bidirectional string assembling systems
RAIRO. Theoretical Informatics and Applications
2014-08-22Paper
Regularity and size of set automata
Descriptional Complexity of Formal Systems
2014-08-07Paper
Oblivious two-way finite automata: decidability and complexity
Information and Computation
2014-07-18Paper
\(\omega \)-rational languages: high complexity classes vs. Borel hierarchy
Language and Automata Theory and Applications
2014-03-31Paper
On the descriptional complexity of the window size for deleting restarting automata
International Journal of Foundations of Computer Science
2014-03-10Paper
One-dimensional cellular automaton transducers
 
2014-02-11Paper
The size impact of little iterative array resources
 
2014-02-05Paper
Non-deterministic cellular automata and languages
International Journal of General Systems
2014-01-06Paper
Time-Symmetric Machines
Reversible Computation
2013-12-17Paper
Size of unary one-way multi-head finite automata
Descriptional Complexity of Formal Systems
2013-08-09Paper
Input-driven queue automata: finite turns, decidability, and closure properties
Implementation and Application of Automata
2013-08-07Paper
One-Way Multi-Head Finite Automata with Pebbles But No States
Developments in Language Theory
2013-06-28Paper
String assembling systems
RAIRO - Theoretical Informatics and Applications
2012-11-22Paper
Reversible pushdown automata
Journal of Computer and System Sciences
2012-11-06Paper
States and heads do count for unary multi-head finite automata
Developments in Language Theory
2012-11-02Paper
On CD-systems of stateless deterministic two-phase RR(1)-automata
Lecture Notes in Computer Science
2012-11-01Paper
Input-driven stack automata
Lecture Notes in Computer Science
2012-09-21Paper
On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata
Implementation and Application of Automata
2012-09-20Paper
On the computational capacity of parallel communicating finite automata
International Journal of Foundations of Computer Science
2012-08-30Paper
The magic number problem for subregular language families
International Journal of Foundations of Computer Science
2012-08-30Paper
Undecidability and hierarchy results for parallel communicating finite automata
International Journal of Foundations of Computer Science
2012-08-29Paper
The complexity of regular(-like) expressions
International Journal of Foundations of Computer Science
2012-08-29Paper
Nondeterministic state complexity of star-free languages
Theoretical Computer Science
2012-08-09Paper
Oblivious two-way finite automata: decidability and complexity
LATIN 2012: Theoretical Informatics
2012-06-29Paper
Descriptional complexity -- an introductory survey
 
2011-12-01Paper
Computational complexity of NURIKABE
Fundamenta Informaticae
2011-11-22Paper
Nature-based problems in cellular automata
Models of Computation in Context
2011-09-09Paper
Gaining Power by Input Operations: Finite Automata and Beyond
Implementation and Application of Automata
2011-07-29Paper
Nodes connected by path languages
Developments in Language Theory
2011-07-29Paper
Nondeterministic state complexity of star-free languages
Implementation and Application of Automata
2011-07-29Paper
Descriptional and computational complexity of finite automata -- a survey
Information and Computation
2011-07-27Paper
Decidability of operation problems for T0L languages and subclasses
Information and Computation
2011-07-27Paper
Cellular automata with limited inter-cell bandwidth
Theoretical Computer Science
2011-07-18Paper
String transformation for \(n\)-dimensional image compression
SOFSEM 2002: Theory and Practice of Informatics
2011-04-01Paper
Two-party Watson-Crick computations
Implementation and Application of Automata
2011-02-11Paper
Cellular automata and the quest for nontrivial artificial self-reproduction
Membrane Computing
2011-01-21Paper
Complexity of multi-head finite automata: origins and directions
Theoretical Computer Science
2011-01-10Paper
On stateless deterministic restarting automata
Acta Informatica
2010-12-13Paper
On stateless two-pushdown automata and restarting automata
International Journal of Foundations of Computer Science
2010-11-11Paper
Cellular automata with sparse communication
Theoretical Computer Science
2010-10-07Paper
Computations and decidability of iterative arrays with restricted communication
Parallel Processing Letters
2010-09-29Paper
Undecidability and hierarchy results for parallel communicating finite automata
Developments in Language Theory
2010-08-31Paper
The complexity of regular(-like) expressions
Developments in Language Theory
2010-08-31Paper
Descriptional complexity of (un)ambiguous finite state machines and pushdown automata
Lecture Notes in Computer Science
2010-08-31Paper
Reversible pushdown automata
Language and Automata Theory and Applications
2010-05-26Paper
Dimension- and time-hierarchies for small time bounds.
Lecture Notes in Computer Science
2010-04-20Paper
Real-time reversible iterative arrays
Theoretical Computer Science
2010-02-09Paper
When Church-Rosser becomes context free
International Journal of Foundations of Computer Science
2010-01-29Paper
Context-free grammars with linked nonterminals
International Journal of Foundations of Computer Science
2010-01-29Paper
On input-revolving deterministic and nondeterministic finite automata
Information and Computation
2009-11-27Paper
Regulated nondeterminism in pushdown automata
Theoretical Computer Science
2009-09-14Paper
NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
International Journal of Foundations of Computer Science
2009-08-21Paper
Self-assembling finite automata
 
2009-08-10Paper
Determination of finite automata accepting subregular languages
Theoretical Computer Science
2009-08-07Paper
Cellular Automata with Sparse Communication
Implementation and Application of Automata
2009-07-09Paper
More on the Size of Higman-Haines Sets: Effective Constructions
Fundamenta Informaticae
2009-06-23Paper
Undecidability of Operation Problems for T0L Languages and Subclasses
Language and Automata Theory and Applications
2009-04-02Paper
Descriptional and Computational Complexity of Finite Automata
Language and Automata Theory and Applications
2009-04-02Paper
Context-Dependent Nondeterminism for Pushdown Automata
Developments in Language Theory
2009-03-26Paper
More on the Size of Higman-Haines Sets: Effective Constructions
Lecture Notes in Computer Science
2009-03-05Paper
Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
Implementation and Applications of Automata
2009-02-12Paper
On Stateless Deterministic Restarting Automata
Lecture Notes in Computer Science
2009-02-03Paper
Deterministic Input-Reversal and Input-Revolving Finite Automata
Language and Automata Theory and Applications
2008-11-20Paper
On the Computational Capacity of Parallel Communicating Finite Automata
Developments in Language Theory
2008-10-30Paper
Succinct description of regular languages by weak restarting automata
Information and Computation
2008-10-08Paper
Fast reversible language recognition using cellular automata
Information and Computation
2008-10-08Paper
OPTIMAL SIMULATIONS OF WEAK RESTARTING AUTOMATA
International Journal of Foundations of Computer Science
2008-09-25Paper
Cellular automata -- a computational point of view
 
2008-09-25Paper
Non-recursive trade-offs for deterministic restarting automata
 
2008-08-12Paper
Efficient pushdown cellular automata: universality, time and space hierarchies
 
2008-07-11Paper
The Boolean closure of linear context-free languages
Acta Informatica
2008-06-17Paper
Regulated Nondeterminism in Pushdown Automata
Implementation and Application of Automata
2008-06-10Paper
HYBRID EXTENDED FINITE AUTOMATA
International Journal of Foundations of Computer Science
2008-05-20Paper
Real-Time Reversible Iterative Arrays
Fundamentals of Computation Theory
2008-02-26Paper
The size of Higman-Haines sets
Theoretical Computer Science
2007-12-19Paper
Hairpin Finite Automata
Developments in Language Theory
2007-11-28Paper
Finite turns and the regular closure of linear context-free languages
Discrete Applied Mathematics
2007-09-21Paper
Cellular devices and unary languages
 
2007-09-12Paper
Hybrid Extended Finite Automata
Implementation and Application of Automata
2007-09-06Paper
Fast Iterative Arrays with Restricted Inter-cell Communication: Constructions and Decidability
Lecture Notes in Computer Science
2007-09-05Paper
Context-dependent nondeterminism for pushdown automata
Theoretical Computer Science
2007-05-11Paper
scientific article; zbMATH DE number 5117088 (Why is no real title available?)
 
2007-01-19Paper
scientific article; zbMATH DE number 5051543 (Why is no real title available?)
 
2006-09-06Paper
Developments in Language Theory
Lecture Notes in Computer Science
2006-06-23Paper
Developments in Language Theory
Lecture Notes in Computer Science
2005-12-22Paper
Developments in Language Theory
Lecture Notes in Computer Science
2005-12-22Paper
Machines, Computations, and Universality
Lecture Notes in Computer Science
2005-12-08Paper
THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
International Journal of Foundations of Computer Science
2005-11-14Paper
NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
International Journal of Foundations of Computer Science
2005-10-19Paper
scientific article; zbMATH DE number 2201358 (Why is no real title available?)
 
2005-09-01Paper
Implementation and Application of Automata
Lecture Notes in Computer Science
2005-08-17Paper
UNSOLVABILITY LEVELS OF OPERATION PROBLEMS FOR SUBCLASSES OF CONTEXT-FREE LANGUAGES
International Journal of Foundations of Computer Science
2005-08-01Paper
On the descriptional complexity of finite automata with modified acceptance conditions
Theoretical Computer Science
2005-02-22Paper
On the descriptional power of heads, counters, and pebbles
Theoretical Computer Science
2005-02-22Paper
scientific article; zbMATH DE number 2113944 (Why is no real title available?)
 
2004-11-05Paper
scientific article; zbMATH DE number 2089986 (Why is no real title available?)
 
2004-08-12Paper
scientific article; zbMATH DE number 2079876 (Why is no real title available?)
 
2004-08-03Paper
scientific article; zbMATH DE number 2068877 (Why is no real title available?)
 
2004-05-27Paper
scientific article; zbMATH DE number 2040920 (Why is no real title available?)
 
2004-02-11Paper
scientific article; zbMATH DE number 2038733 (Why is no real title available?)
 
2004-02-08Paper
Fast one-way cellular automata.
Theoretical Computer Science
2003-08-17Paper
scientific article; zbMATH DE number 1962776 (Why is no real title available?)
 
2003-08-11Paper
scientific article; zbMATH DE number 1949654 (Why is no real title available?)
 
2003-07-15Paper
scientific article; zbMATH DE number 1948495 (Why is no real title available?)
 
2003-07-13Paper
scientific article; zbMATH DE number 1886323 (Why is no real title available?)
 
2003-03-19Paper
Massively parallel fault tolerant computations on syntactical patterns
Future Generation Computer Systems
2003-01-21Paper
Deterministic Turing machines in the range between real-time and linear-time.
Theoretical Computer Science
2003-01-21Paper
scientific article; zbMATH DE number 1836417 (Why is no real title available?)
 
2002-11-27Paper
scientific article; zbMATH DE number 1834667 (Why is no real title available?)
 
2002-11-25Paper
scientific article; zbMATH DE number 1759473 (Why is no real title available?)
 
2002-11-25Paper
scientific article; zbMATH DE number 1759411 (Why is no real title available?)
 
2002-11-04Paper
scientific article; zbMATH DE number 1738667 (Why is no real title available?)
 
2002-05-07Paper
On tally languages and generalized interacting automata
 
2001-04-04Paper
scientific article; zbMATH DE number 1390061 (Why is no real title available?)
 
2000-10-03Paper
scientific article; zbMATH DE number 714577 (Why is no real title available?)
 
2000-06-21Paper
On time reduction and simulation in cellular spaces
International Journal of Computer Mathematics
1999-09-01Paper
scientific article; zbMATH DE number 1222612 (Why is no real title available?)
 
1999-06-21Paper
Pushdown cellular automata
Theoretical Computer Science
1999-04-28Paper
On time computability of functions in one-way cellular automata
Acta Informatica
1998-08-20Paper
scientific article; zbMATH DE number 815072 (Why is no real title available?)
 
1995-11-12Paper
scientific article; zbMATH DE number 4209629 (Why is no real title available?)
 
1991-01-01Paper


Research outcomes over time


This page was built for person: Martin Kutrib